ford_fulkerson_flow

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

Return a maximum flow for a single-commodity flow problem.

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_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)
>>> F = nx.ford_fulkerson_flow(G, 'x', 'y')
>>> for u, v in G.edges_iter():
...     print('(%s, %s) %.2f' % (u, v, F[u][v]))
... 
(a, c) 2.00
(c, y) 2.00
(b, c) 0.00
(b, d) 1.00
(e, y) 1.00
(d, e) 1.00
(x, a) 2.00
(x, b) 1.00