# 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 1flow increased by 6 at path ['A', 'D', 'F', 'H'] ; current flow 7flow increased by 1 at path ['A', 'C', 'G', 'H'] ; current flow 8flow increased by 4 at path ['A', 'C', 'E', 'H'] ; current flow 12flow 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 5flow increased by 4 at path ['A', 'B', 'E', 'C', 'F', 'H'] ; current flow 9flow increased by 2 at path ['A', 'D', 'F', 'C', 'E', 'H'] ; current flow 11flow increased by 1 at path ['A', 'D', 'F', 'C', 'G', 'H'] ; current flow 12flow increased by 2 at path ['A', 'D', 'F', 'H'] ; current flow 14flow increased by 1 at path ['A', 'D', 'G', 'H'] ; current flow 15`