before I dive into the question here is some background information of what I already have:
-I first created an non-directed adjacency matrix graph based on cities across U.S. with edge weights being the calculated distance (achieved that through distance formula).
-I also implemented a minimum spanning tree using prim's algorithm.
Now I need to implement Edmonds Karp maximum flow algorithm which I have but I am confused on how would I create a capacity graph based on the data I have in order to implement the algorithm used in the following code:
def edmonds_karp(C, source, sink):
n = len(C) # C is the capacity matrix
F = [[0] * n for i in xrange(n)]
# residual capacity from u to v is C[u][v] - F[u][v]
while True:
path = bfs(C, F, source, sink)
if not path:
break
# traverse path to find smallest capacity
flow = min(C[u][v] - F[u][v] for u,v in path)
# traverse path to update flow
for u,v in path:
F[u][v] += flow
F[v][u] -= flow
return sum(F[source][i] for i in xrange(n))
def bfs(C, F, source, sink):
queue = [source]
paths = {source: []}
while queue:
u = queue.pop(0)
for v in xrange(len(C)):
if C[u][v] - F[u][v] > 0 and v not in paths:
paths[v] = paths[u] + [(u,v)]
if v == sink:
return paths[v]
queue.append(v)
return None
Any help will be greatly appreciated, thank you!
All what it needed to do for Edmonds-Karp algorithm is to change the weights of all of the edges into 1 because they are not needed in order to find the edge connectivity between cities in this problem. And the graph of the cities with edge weights being 1 is going to be my capacity graph. Also for Edmonds-Karp algorithm will need to have a directed graph.