Find the value of maximum single-commodity flow.
Parameters: | G : NetworkX graph
s : node
t : node
capacity : string
flow_func : function
kwargs : Any other keyword parameter is passed to the function that
|
---|---|
Returns: | flow_value : integer, float
|
Raises: | NetworkXError :
NetworkXUnbounded :
|
See also
maximum_flow(), minimum_cut(), minimum_cut_value(), edmonds_karp(), ford_fulkerson(), preflow_push(), shortest_augmenting_path()
Notes
The function used in the flow_func paramter has to return a residual network that follows NetworkX conventions:
The residual network R from an input graph G has the same nodes as G. R is a DiGraph that contains a pair of edges (u, v) and (v, u) iff (u, v) is not a self-loop, and at least one of (u, v) and (v, u) exists in G.
For each edge (u, v) in R, R[u][v]['capacity'] is equal to the capacity of (u, v) in G if it exists in G or zero otherwise. If the capacity is infinite, R[u][v]['capacity'] will have a high arbitrary finite value that does not affect the solution of the problem. This value is stored in R.graph['inf']. For each edge (u, v) in R, R[u][v]['flow'] represents the flow function of (u, v) and satisfies R[u][v]['flow'] == -R[v][u]['flow'].
The flow value, defined as the total flow into t, the sink, is stored in R.graph['flow_value']. Reachability to t using only edges (u, v) such that R[u][v]['flow'] < R[u][v]['capacity'] induces a minimum s-t cut.
Specific algorithms may store extra data in R.
The function should supports an optional boolean parameter value_only. When True, it can optionally terminate the algorithm as soon as the maximum flow value and the minimum cut can be determined.
The legacy ford_fulkerson() maximum flow implementation doesn’t follow this conventions but it is supported as a valid flow_func.
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)
maximum_flow_value computes only the value of the maximum flow:
>>> flow_value = nx.maximum_flow_value(G, 'x', 'y')
>>> flow_value
3.0
You can also use alternative algorithms for computing the maximum flow by using the flow_func parameter.
>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> flow_value == nx.maximum_flow_value(G, 'x', 'y',
... flow_func=shortest_augmenting_path)
True