ford_fulkerson

ford_fulkerson(G, s, t, capacity='capacity')

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

This algorithm uses Edmonds-Karp-Dinitz path selection rule which guarantees a running time of O(nm^2) for n nodes and m edges.

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.

capacity: string :

Edges of the graph G are expected to have an attribute capacity that indicates how much flow the edge can support. If this attribute is not present, the edge is considered to have infinite capacity. Default value: ‘capacity’.

Returns :

flow_value : integer, float

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

flow_dict : dictionary

Dictionary of dictionaries keyed by nodes such that flow_dict[u][v] is the flow edge (u, v).

Raises :

NetworkXError :

The algorithm does not support MultiGraph and MultiDiGraph. If the input graph is an instance of one of these two classes, a NetworkXError is raised.

NetworkXUnbounded :

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 NetworkXUnbounded.

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