Day 49: Ford-Fulkerson

Tonight I heard a strange noise coming out of my bathroom. After a quick check I found there’s a small unplanned fountain in my wall.

It was 3:30AM and as I was waiting for emergency service to arrive, I thought it would be a good idea to implement Ford-Fulkerson today.

It is an algorithm that finds a maximum flow between source and sink node in directed graph. There are two conditions.

  • each edge in the graph has a fixed capacity and a flow through the edge must not exceed the capacity
  • total incoming flow into any node must be equal to total outgoing flow from the node

Ford-Fulkerson greedily searches for a path between source and sink, such that each edge along the path still has a capacity reserve. If such path exists, the flow along the path gets increased.

However, the path is allowed to go through an edge in inverse direction. If there is any flow on such edge, it gets decreased, instead. This step effectively redirects flow from the edge and increases its capacity reserve, while total flow in graph increases.

note to Python version

If you use Python 3.6 the algorithm behaves deterministically due to a new dictionary implementation. Python 3.5 should return different results on different runs. In which case you can witness a selection of inverted edges and increases of capacity reserves, such as path ADFCGH below.

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

algorithm

def ford_fulkerson(graph, source, sink, debug=None):
flow, path = 0, True

while path:
# search for path with flow reserve
path, reserve = depth_first_search(graph, source, sink)
flow += reserve
        # increase flow along the path
for v, u in zip(path, path[1:]):
if graph.has_edge(v, u):
graph[v][u]['flow'] += reserve
else:
graph[u][v]['flow'] -= reserve

# show intermediate results
if callable(debug):
debug(graph, path, reserve, flow)

def depth_first_search(graph, source, sink):
undirected = graph.to_undirected()
explored = {source}
stack = [(source, 0, undirected[source])]

while stack:
v, _, neighbours = stack[-1]
if v == sink:
break

# search the next neighbour
while neighbours:
u, e = neighbours.popitem()
if u not in explored:
break
else:
stack.pop()
continue

# current flow and capacity
in_direction = graph.has_edge(v, u)
capacity = e['capacity']
flow = e['flow']
        # increase or redirect flow at the edge
if in_direction and flow < capacity:
stack.append((u, capacity - flow, undirected[u]))
explored.add(u)
elif not in_direction and flow:
stack.append((u, flow, undirected[u]))
explored.add(u)
    # (source, sink) path and its flow reserve
reserve = min((f for _, f, _ in stack[1:]), default=0)
path = [v for v, _, _ in stack]

return path, reserve

graph

graph = nx.DiGraph()
graph.add_nodes_from('ABCDEFGH')
graph.add_edges_from([
('A', 'B', {'capacity': 4, 'flow': 0}),
('A', 'C', {'capacity': 5, 'flow': 0}),
('A', 'D', {'capacity': 7, 'flow': 0}),
('B', 'E', {'capacity': 7, 'flow': 0}),
('C', 'E', {'capacity': 6, 'flow': 0}),
('C', 'F', {'capacity': 4, 'flow': 0}),
('C', 'G', {'capacity': 1, 'flow': 0}),
('D', 'F', {'capacity': 8, 'flow': 0}),
('D', 'G', {'capacity': 1, 'flow': 0}),
('E', 'H', {'capacity': 7, 'flow': 0}),
('F', 'H', {'capacity': 6, 'flow': 0}),
('G', 'H', {'capacity': 4, 'flow': 0}),
])

max flow, Python 3.6

check github for full output

> ford_fulkerson(graph, 'A', 'H', flow_debug)
flow increased by 1 at path ['A', 'D', 'G', 'H'] ; current flow 1
flow increased by 6 at path ['A', 'D', 'F', 'H'] ; current flow 7
flow increased by 1 at path ['A', 'C', 'G', 'H'] ; current flow 8
flow increased by 4 at path ['A', 'C', 'E', 'H'] ; current flow 12
flow increased by 3 at path ['A', 'B', 'E', 'H'] ; current flow 15

max flow, Python 3.5

check Azure notebooks for full output

> ford_fulkerson(graph, 'A', 'H', flow_debug)
flow increased by 5 at path ['A', 'C', 'E', 'H'] ; current flow 5
flow increased by 4 at path ['A', 'B', 'E', 'C', 'F', 'H'] ; current flow 9
flow increased by 2 at path ['A', 'D', 'F', 'C', 'E', 'H'] ; current flow 11
flow increased by 1 at path ['A', 'D', 'F', 'C', 'G', 'H'] ; current flow 12
flow increased by 2 at path ['A', 'D', 'F', 'H'] ; current flow 14
flow increased by 1 at path ['A', 'D', 'G', 'H'] ; current flow 15
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.