flow.py

import collections
import Queue

def dijkstra(graph, source, sink):

  q = Queue.PriorityQueue()
  q.put((0, source, []))
  visited = set([source])

  while not q.empty():
      length, node, path = q.get()

      # Found a path return the capacity
      if node == sink:
          cap = None
          for a, b in path:
              if cap is None or graph[a][b] < cap:
                  cap = graph[a][b]
          return cap, path

      # Visit next node
      for child in graph[node].keys():
          if not child in visited and graph[node][child] > 0:
              next_state = (length+1, child, path + [(node, child)])
              visited.add(child)
              q.put(next_state)

  # No paths remaining
  return None, None

def max_flow(graph, source, sink):

    flow = 0

    while True:
        capacity, path = dijkstra(graph, source, sink)
        if not capacity: return flow

        for a, b in path:
            graph[a][b] = graph[a].get(b, 0) - capacity
            graph[b][a] = graph[b].get(a, 0) + capacity
        flow += capacity

    return flow