Floyd Warshall Algorithm in python

# The number of vertices
nV = 4

INF = 999

# Algorithm implementation
def floyd_warshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))

# Adding vertices individually
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)

# Printing the solution
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:
print(distance[i][j], end=" ")
print(" ")

G = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
floyd_warshall(G)

-------------------------------------------------------------------------------------------------------------------------------------

# Dijkstra's Algorithm in Python

import sys

# Providing the graph
vertices = [[0, 0, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 0],
[1, 1, 0, 1, 1, 0, 0],
[1, 0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 0, 1, 0]]

edges = [[0, 0, 1, 2, 0, 0, 0],
[0, 0, 2, 0, 0, 3, 0],
[1, 2, 0, 1, 3, 0, 0],
[2, 0, 1, 0, 0, 0, 1],
[0, 0, 3, 0, 0, 2, 0],
[0, 3, 0, 0, 2, 0, 1],
[0, 0, 0, 1, 0, 1, 0]]

# Find which vertex is to be visited next
def to_be_visited():
global visited_and_distance
v = -10
for index in range(num_of_vertices):
if visited_and_distance[index][0] == 0 \
and (v < 0 or visited_and_distance[index][1] <=
visited_and_distance[v][1]):
v = index
return v

num_of_vertices = len(vertices[0])

visited_and_distance = [[0, 0]]
for i in range(num_of_vertices-1):
visited_and_distance.append([0, sys.maxsize])

for vertex in range(num_of_vertices):

# Find next vertex to be visited
to_visit = to_be_visited()
for neighbor_index in range(num_of_vertices):

# Updating new distances
if vertices[to_visit][neighbor_index] == 1 and \
visited_and_distance[neighbor_index][0] == 0:
new_distance = visited_and_distance[to_visit][1] \
+ edges[to_visit][neighbor_index]
if visited_and_distance[neighbor_index][1] > new_distance:
visited_and_distance[neighbor_index][1] = new_distance

visited_and_distance[to_visit][0] = 1

i = 0

# Printing the distance
for distance in visited_and_distance:
print("Distance of ", chr(ord('a') + i),
" from source vertex: ", distance[1])
i = i + 1

__________________________________________________________________________________________________________

# Bellman Ford Algorithm in Python

class Graph:

def __init__(self, vertices):
self.V = vertices # Total number of vertices in the graph
self.graph = [] # Array of edges

# Add edges
def add_edge(self, s, d, w):
self.graph.append([s, d, w])

# Print the solution
def print_solution(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("{0}\t\t{1}".format(i, dist[i]))

def bellman_ford(self, src):

# Step 1: fill the distance array and predecessor array
dist = [float("Inf")] * self.V
# Mark the source vertex
dist[src] = 0

# Step 2: relax edges |V| - 1 times
for _ in range(self.V - 1):
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
dist[d] = dist[s] + w

# Step 3: detect negative cycle
# if value changes then we have a negative cycle in the graph
# and we cannot find the shortest distances
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
print("Graph contains negative weight cycle")
return

# No negative weight cycle found!
# Print the distance and predecessor array
self.print_solution(dist)

g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)

g.bellman_ford(0)

--------------------------------------------------------------------------------------------------------------------------------------------

Linear Search
from random import randint
list = [randint(1, 100) for i in range(10)]
list

key = int(input("Enter the key value:"))
if key in list:
print("Element is found in the list")
else:
print("Element is not found in the list")

import time
import psutil
import matplotlib.pyplot as plt

arr = list(range(100000, 0, -1))

def bubble sort (arr):
n = len(arr)
for i in range(n):
for j in range(e, n-i-1):
if arr[j] > arr[j+1] :
are[j], arr[j+1] = arr[j+1], arr[j]

times = []
memories = []

for n in range(1000, 100001, 1000):
# Record time taken
start_time = time.time()
bubble_sort(arr[:n])
end_time = time.time()
times.append(end_time - start_time)
# Record memory used
process = psutil.Process()
mem = process.memory_info().rss / 1024 / 1024
memories.append(mem)

arr = [-4, 3, -9, 0, 4, 1]
print(arr)
neg_count, pos_count,wqual_count = 0,0,0
count = len(arr)
neg_count = len(list(filter(lambda x: (x < 0), arr))
pos_count = len(list(filter(lambda x: (x > 0), arr))
eql_count = len(list(filter(lambda x: (x == 0), arr))
print(pos_count)
print(neg_count)
print(eql_count)
print(pos_count / count)
print(neg_count / count)
print(eql_count / count)

arr= [1,2,3,4,5]

==================================================================================
Edmonds Karp ALGORITHMS

import decimal
def EdmondsKarp(E, C, s, t):
n = len(C)
flow = 0
F = [[0 for y in range(n)] for x in range(n)]
while True:
P = [-1 for x in range(n)]
P[s] = -2
M= [0 for x in range(n)]
M[s] = decimal. Decimal( Infinity')
BFSq = []
BFSq.append(s)
pathFlow, P = BFSEK(E, C, s, t, F, P, M, BFSq)
if pathFlow == 0:
break
flow = flow + pathFlow
v = t
while v != s:
u = P[v]
F[u][v] = F[u][v] + pathFlow
F[v][u] = F[v][u] - pathFlow
v = u
return flow
def BFSEK (E, C, s, t, F, P, M, BFSq):
while (len(BFSq) > 0):
u= BFSq.pop(0)
for v in E[u]:
if C[u][v] F[u][v]> 0 and P[v] == -1:
P[v] = u
M[v] = min(M[u], C[u][v] - F[u][v])
if v != t:
BFSq.append(v)
else:
return M[t], P
return 0, P
E = [[1, 2], [2, 3], [3], []]
C= [[8, 1000000, 1000000, 0], [0, 0, 1, 1000000], [0,0, 0, 1000000], [0, 0, 0, 0]]
s=0
t=0
EdmondsKarp(E, C, s, t)

==================================================================================
parallel all-pairs shotest path algorithm

import concurrent, futures
import sys
INF = float('inf')
def Floyd_warshall (graph):
num vertices = len(graph)
dist = [[INF] *num_vertices for _ in range(num_vertices)]
for i in range(num_vertices):
for j in range(num_vertices):
if i == j:
dist[i][j] = 0
elif graph[i][j] != 0:
dist[i][j] = graph[i][j]
for k in range(num_vertices):
for i in range(num_vertices):
for i in range(num_vertices):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
def parallel_all_pairs_shortest_path(graph):
num_vertices = len(graph)
with concurrent.futures.ThreadPoolExecutor(max_workers=num_vertices) as executor:
futures = []
for i in range(num_vertices):

futures.append(executor.submit(floyd_warshall, graph))
results = [future.result() for future in futures]
final_result = [[INF] * num_vertices for_ in range(num_vertices)]

for result in results:
for i in range(num_vertices):
for j in range(num_vertices):
final result[i][j] = min(final result[i][j], result[i]

return final_result

#Example usage

If__name__==”__main__”:

graph = [
[0, 3, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 7, 0, 2],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 2, 0, 3],
[0, 0, 0, 0, 0, 0]
]

shortest paths parallel_all_pairs_shortest_path(graph)

for i in range(len(shortest_paths)):
for j in range(len(shortest paths[i])):
if shortest paths[i][j]=INF:
print("INF", end="\t")
else:
print(shortest paths[i][1], end-"\t")
print()

==================================================================================

#Tarjan's Strongly Connected Componenet algorithm

from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
self.Time=0
def addEdge(self, u, v):
self.graph[u].append(v)
def SCCUtil(self, u, low, disc, stackMember, st):
disc[u] = self.Time
low[u] = self.Time
self.Time += 1
stackMember [u] = True
st.append(u)
for v in self.graph[u]:
if disc[v] == -1:
self.SCCUtil(v, low, disc, stackMember, st)
low[u] min(low[u], low[v])
elif stackMember[v] == True:

low[u] = min(low[u], disc[v])
W = -1
if low[u] == disc[u]:
while w != U:
w = st.pop()
print (w, end=” ”)
stackMember [w] = False
print()

def SCC(self):
disc = [-1] * (self.V)
low = [-1] * (self.V)
stackMember = [False] * (self.v)
st = []

for i in range(self.V):
if disc[i] == -1:
self.SCCUtil(i, low, disc, stackMember, st)
# Create a graph given in the above diagram
g1 = Graph (5)
g1.addEdge (1, 0)
g1.addEdge(0, 2)
g1.addEdge (2, 1)
g1.addEdge(0, 3)
g1.addEdge (3, 4)
print("SSC in first graph ")
g2.SCC()

g2= Graph (4)
g2.addEdge(0, 1)
g2.addEdge (1, 2)
g2.addEdge (2, 3)
print("\nSSC in second graph ")
g2.SCC()

g3 = Graph(7)
g3.addEdge (0, 1)
g3.addEdge (1, 2)
g3.addEdge (2, 0)
g3.addEdge (1, 3)
g3.addEdge (1, 4)
g3.addEdge (1, 6)
g3.addEdge (3, 5)
g3.addEdge (4, 5)
print("\nSSC in third graph ")
g3.SCC()

g4 = Graph(11)
g4.addEdge(0, 1)
g4.addEdge(0,3)
g4.addEdge(1, 2)
g4.addEdge(1, 4)
g4.addEdge(2, 0)
g4.addEdge(2, 6)
g4.addEdge(3, 2)
g4.addEdge(4, 5)
g4.addEdge(4, 6)
g4.addEdge(5, 6)
g4.addEdge(5, 7)
g4.addEdge(5, 8)
g4.addEdge(5, 9)
g4.addEdge(6, 4)
g4.addEdge(7, 9)
g4.addEdge(8, 9)
g4.addEdge(9, 8)
print(“\nSSC in fourth graph”)
g4.ssc()

g5 = Graph(5)
g5.addEdge(0,1)
g5.addEdge(1,2)
g5.addEdge(2,3)
g5.addEdge(2,4)
g5.addEdge(3,0)
g5.addEdge(4,2)
print(“\nSSC in fifth graph ”)
g5.SCC()

==================================================================================

POLICE CHASE PROBLEM
# Python3 program to find maximum
# number of thieves caught

# Returns maximum number of thieves
# that can be caught.

def policeThief(arr, n, k):
i = 0
l = 0
r = 0
res = 0
thi = []
pol = []

# store indices in list
while i < n:
if arr[i] == 'P':
pol.append(i)
elif arr[i] == 'T':
thi.append(i)
i += 1

# track lowest current indices of
# thief: thi[l], police: pol[r]
while l < len(thi) and r < len(pol):

# can be caught
if (abs(thi[l] - pol[r]) <= k):
res += 1
l += 1
r += 1

# increment the minimum index
elif thi[l] < pol[r]:
l += 1
else:
r += 1

return res

# Driver program
if __name__ == '__main__':
arr1 = ['P', 'T', 'T', 'P', 'T']
k = 2
n = len(arr1)
print(("Maximum thieves caught: {}".
format(policeThief(arr1, n, k))))

arr2 = ['T', 'T', 'P', 'P', 'T', 'P']
k = 2
n = len(arr2)
print(("Maximum thieves caught: {}".
format(policeThief(arr2, n, k))))

arr3 = ['P', 'T', 'P', 'T', 'T', 'P']
k = 3
n = len(arr3)
print(("Maximum thieves caught: {}".
format(policeThief(arr3, n, k))))

# This code is contributed by `jahid_nadim`
____________________________________________________________________________________________________________

FINDING POTENTIAL PROBLEM
# Python3 program to find all pairs in
# a list of integers with given sum
from collections import Counter

def findPairs(lst, K):
res = []
count = Counter(lst)

for x in lst:
y = K - x
if (x != y and count[y]) or (x == y and count[y] > 1):
res.append((x, y))
count.subtract((x, y))

return res

# Driver code
lst = [1, 5, 3, 7, 9]
K = 12
print(findPairs(lst, K))
__________________________________________________________________________________________________________

EUCLIDEAN LEMMA
def extended_euclidean(a, b):
if b == 0:
gcd, s, t = a, 1, 0
return (gcd, s, t)
else:
s2, t2, s1, t1 = 1, 0, 0, 1
while b > 0:
q= a // b
r, s, t = (a - b * q),(s2 - q * s1),( t2 - q * t1)
a,b,s2,t2,s1,t1=b,r,s1,t1,s,t
gcd,s,t=a,s2,t2
return (gcd,s,t)
#Take input
print("Input two non-negative integers a and b such that a>=b")
a, b = map(int, input().split())
x, y = a, b # Store temporarily
result=extended_euclidean(a,b)
#Print the result
print(f"gcd({x},{y})={result[0]}")
print(f"Linear combination gcd(a,b)=sa+tb:\n {result[0]}={result[1]}{x}+{result[2]}{y}")

_______________________________________________________________________________________________________

CATALAN NUMBERS

# A dynamic programming based function to find nth
# Catalan number

def catalan(n):
if (n == 0 or n == 1):
return 1

# Table to store results of subproblems
catalan = [0 for i in range(n + 1)]

# Initialize first two values in table
catalan[0] = 1
catalan[1] = 1

# Fill entries in catalan[] using recursive formula
for i in range(2, n + 1):
catalan[i] = 0
for j in range(i):
catalan[i] += catalan[j] * catalan[i-j-1]

# Return last entry
return catalan[n]

# Driver code
for i in range(10):
print(catalan(i))