ford_fulkerson¶

ford_fulkerson(G, s, t, capacity='capacity')[source]¶

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.

See also

maximum_flow(), minimum_cut(), edmonds_karp(), preflow_push(), shortest_augmenting_path()

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)