# 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