Skip to content

Instantly share code, notes, and snippets.

@juanplopes
Last active August 29, 2015 14:02
Show Gist options
  • Save juanplopes/178060e556e68421a8c5 to your computer and use it in GitHub Desktop.
Save juanplopes/178060e556e68421a8c5 to your computer and use it in GitHub Desktop.
Ford-Fulkerson example for presentation: http://goo.gl/DizfF7
from collections import defaultdict
def add(network, a, b, capacity):
network[a][b] = network[b][a] = capacity
def send(network, a, b, V, minimum=1000000):
V.add(a)
if a == b:
print '-> path', a
return minimum
for node, capacity in network[a].items():
if node in V or capacity == 0: continue
sent = send(network, node, b, V, min(minimum, capacity))
if sent>0:
print '-> path', a, capacity
network[a][node] -= sent
network[node][a] += sent
return sent
return 0
network = defaultdict(lambda : {})
add(network, 'ford', 'A', 10)
add(network, 'ford', 'B', 100)
add(network, 'A', 'B', 50)
add(network, 'A', 'C', 20)
add(network, 'A', 'D', 10)
add(network, 'B', 'D', 1)
add(network, 'C', 'D', 30)
add(network, 'C', 'E', 100)
add(network, 'D', 'E', 200)
add(network, 'D', 'F', 5)
add(network, 'E', 'F', 100)
add(network, 'E', 'fulkerson', 3)
add(network, 'F', 'fulkerson', 200)
total = 0
while True:
sent = send(network, 'ford', 'fulkerson', set())
print 'Sent:', sent
if not sent: break
total += sent
print 'Final value:', total
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment