FordFulkerson module¶

The Ford-Fulkerson Algorithm find the maximum flow in a network, a directed graph from a source vertex s to a target vertex t. Each edge in the graph has a capacity which may not be exceeded by the flow running through the graph. Additionally, the amount of flow into a vertex must equal the flow out of that vertex.

The Ford-Fulkerson algorithm finding the maximum flow using the concept of augmenting paths. An augmenting path in a network is a path form s to t using only edges with have residual capacity. If there are no such paths, then the flow is maximum. Forward edges follow the direction of the arc in the network while backwards edges move against the arc in the network. Backwards edges can have there flow reduced to increase the overall flow of the network

Algorithm 10.2.2 on page 201

FordFulkerson.augment_flow(N, t, prev_pt, res_cap)¶

Take the augmenting path to t and increase the flow so that it is no longer augmenting

All operations are done in place to the network N. The prev_pt of the start of the path is assumed to be None.

Parameters

Nnx.DiGraph

The network with contains the augmenting path

tint

The terminal vertex of the augmenting path

prev_ptDict

A mapping of the vertices to the predecessor vertex in the path

res_capDict

A mapping from vertex v to the residual capacity of the s-v path

FordFulkerson.ford_fulkerson(N, s, t)¶

Performs the Ford-Fulkerson Algorithm on the given network to find the maximum flow of the network.

Results of the algorithm are stored in place in N and the value of the flow is returned. Edge attribute capacity is assumed to set for each edge

Parameters

Nnx.DiGraph

sint

The source vertex of the network

tint

The target vertex of the network

Returns

int

The value of the maximum flow