networkx.ford_fulkerson

ford_fulkerson(G, s, t)

Find a maximum single-commodity flow using the Ford-Fulkerson algorithm.

This algorithm uses Edmond-Karp-Dinitz path selection rule which guarantees a running time of O(|V||E|**2).

Parameters:

G : NetworkX graph

Edges of the graph are expected to have an attribute called ‘capacity’. If this attribute is not present, the edge is considered to have infinite capacity.

s : node

Source node for the flow.

t : node

Sink node for the flow.

Returns:

flowValue : integer, float

Value of the maximum flow, i.e., net outflow from the source.

flowGraph : NetworkX graph

Graph with V(flowGraph) = V(G) and in which each edge has an attribute ‘flow’ which gives the flow on the edge.

Raises:

NetworkXError :

If the graph has a path of infinite capacity, the value of a feasible flow on the graph is unbounded above and the function raises a NetworkXError.

Examples

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge('x','a', capacity = 3.0)
>>> G.add_edge('x','b', capacity = 1.0)
>>> G.add_edge('a','c', capacity = 3.0)
>>> G.add_edge('b','c', capacity = 5.0)
>>> G.add_edge('b','d', capacity = 4.0)
>>> G.add_edge('d','e', capacity = 2.0)
>>> G.add_edge('c','y', capacity = 2.0)
>>> G.add_edge('e','y', capacity = 3.0)
>>> flow,F=nx.ford_fulkerson(G, 'x', 'y')
>>> flow
3.0