Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

ford_fulkerson

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

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

This is the legacy implementation of maximum flow. See Notes below.

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 :

R : NetworkX DiGraph

The residual network after computing the maximum flow. This is a legacy implementation, se Notes and Examples.

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.

Notes

This is a legacy implementation of maximum flow (before 1.9). This function used to return a tuple with the flow value and the flow dictionary. Now it returns the residual network resulting after computing the maximum flow, in order to follow the new interface to flow algorithms introduced in NetworkX 1.9.

Note however that the residual network returned by this function does not follow the conventions for residual networks used by the new algorithms introduced in 1.9. This residual network has edges with capacity equal to the capacity of the edge in the original network minus the flow that went throught that edge. A dictionary with infinite capacity edges can be found as an attribute of the residual network.

Examples

>>> import networkx as nx
>>> from networkx.algorithms.flow import ford_fulkerson

The functions that implement flow algorithms and output a residual network, such as this one, are not imported to the base NetworkX namespace, so you have to explicitly import them from the flow package.

>>> 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)

This function returns the residual network after computing the maximum flow. This network has graph attributes that contain: a dictionary with edges with infinite capacity flows, the flow value, and a dictionary of flows:

>>> R = ford_fulkerson(G, 'x', 'y')
>>> # A dictionary with infinite capacity flows can be found as an
>>> # attribute of the residual network
>>> inf_capacity_flows = R.graph['inf_capacity_flows']
>>> # There are also attributes for the flow value and the flow dict
>>> flow_value = R.graph['flow_value']
>>> flow_dict = R.graph['flow_dict']

You can use the interface to flow algorithms introduced in 1.9 to get the output that the function ford_fulkerson used to produce:

>>> flow_value, flow_dict = nx.maximum_flow(G, 'x', 'y',
...                                         flow_func=ford_fulkerson)