I am trying to implement a version of the Edmonds–Karp algorithm for an undirected graph. The code below works, but it is very slow when working with big matrices.
Is it possible to get the Edmonds–Karp algorithm to run faster, or should I proceed to another algorithm, like "Push Relabel"? I have though of some kind of dequeue working with the bfs, but I don't know how to do that.
The code:
def bfs(C, F, s, t):
stack = [s]
paths={s:[]}
if s == t:
return paths[s]
while(stack):
u = stack.pop()
for v in range(len(C)):
if(C[u][v]-F[u][v]>0) and v not in paths:
paths[v] = paths[u]+[(u,v)]
if v == t:
return paths[v]
stack.append(v)
return None
def maxFlow(C, s, t):
n = len(C) # C is the capacity matrix
F = [[0] * n for i in range(n)]
path = bfs(C, F, s, t)
while path != None:
flow = min(C[u][v] - F[u][v] for u,v in path)
for u,v in path:
F[u][v] += flow
F[v][u] -= flow
path = bfs(C,F,s,t)
return sum(F[s][i] for i in range(n))
C = [[ 0, 3, 3, 0, 0, 0 ], # s
[ 3, 0, 2, 3, 0, 0 ], # o
[ 0, 2, 0, 0, 2, 0 ], # p
[ 0, 0, 0, 0, 4, 2 ], # q
[ 0, 0, 0, 2, 0, 2 ], # r
[ 0, 0, 0, 0, 2, 0 ]] # t
source = 0 # A
sink = 5 # F
maxVal = maxFlow(C, source, sink)
print("max_flow_value is: ", maxVal)
I think your solution can benefit from better graph representation. In particular try to keep a list of neighbours for the BFS. I actually wrote a quite long answer on the graph representation I use for flow algorithms here https://stackoverflow.com/a/23168107/812912
If your solution is still too slow I would recommend switching to Dinic's algorithm it has served me well in many tasks.