maximum_flow_value#

maximum_flow_value(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[source]#

Find the value of maximum single-commodity flow.

Parameters:

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

_snode

Source node for the flow.

_tnode

Sink node for the flow.

capacitystring or function (default= ‘capacity’)

If this is a string, then edge capacity will be accessed via the edge attribute with this key (that is, the capacity of the edge joining u to v will be G.edges[u, v][capacity]). If no such edge attribute exists, the capacity of the edge is assumed to be infinite.

If this is a function, the capacity of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None to indicate a hidden edge.

flow_funcfunction

A function for computing the maximum flow among a pair of nodes in a capacitated graph. The function has to accept at least three parameters: a Graph or Digraph, a source node, and a target node. And return a residual network that follows NetworkX conventions (see Notes). If flow_func is None, the default maximum flow function (preflow_push()) is used. See below for alternative algorithms. The choice of the default function may change from version to version and should not be relied on. Default value: None.

kwargsAny other keyword parameter is passed to the function that

computes the maximum flow.

Returns:

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

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()
minimum_cut_value()
edmonds_karp()
preflow_push()
shortest_augmenting_path()

Notes

The function used in the flow_func parameter 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.

Examples

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