"""
Edmonds-Karp algorithm for maximum flow problems.
"""
import networkx as nx
from networkx.algorithms.flow.utils import build_residual_network
__all__ = ["edmonds_karp"]
def edmonds_karp_core(R, s, t, cutoff):
"""Implementation of the Edmonds-Karp algorithm."""
R_nodes = R.nodes
R_pred = R.pred
R_succ = R.succ
inf = R.graph["inf"]
def augment(path):
"""Augment flow along a path from s to t."""
# Determine the path residual capacity.
flow = inf
it = iter(path)
u = next(it)
for v in it:
attr = R_succ[u][v]
flow = min(flow, attr["capacity"] - attr["flow"])
u = v
if flow * 2 > inf:
raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
# Augment flow along the path.
it = iter(path)
u = next(it)
for v in it:
R_succ[u][v]["flow"] += flow
R_succ[v][u]["flow"] -= flow
u = v
return flow
def bidirectional_bfs():
"""Bidirectional breadth-first search for an augmenting path."""
pred = {s: None}
q_s = [s]
succ = {t: None}
q_t = [t]
while True:
q = []
if len(q_s) <= len(q_t):
for u in q_s:
for v, attr in R_succ[u].items():
if v not in pred and attr["flow"] < attr["capacity"]:
pred[v] = u
if v in succ:
return v, pred, succ
q.append(v)
if not q:
return None, None, None
q_s = q
else:
for u in q_t:
for v, attr in R_pred[u].items():
if v not in succ and attr["flow"] < attr["capacity"]:
succ[v] = u
if v in pred:
return v, pred, succ
q.append(v)
if not q:
return None, None, None
q_t = q
# Look for shortest augmenting paths using breadth-first search.
flow_value = 0
while flow_value < cutoff:
v, pred, succ = bidirectional_bfs()
if pred is None:
break
path = [v]
# Trace a path from s to v.
u = v
while u != s:
u = pred[u]
path.append(u)
path.reverse()
# Trace a path from v to t.
u = v
while u != t:
u = succ[u]
path.append(u)
flow_value += augment(path)
return flow_value
def edmonds_karp_impl(G, s, t, capacity, residual, cutoff):
"""Implementation of the Edmonds-Karp algorithm."""
if s not in G:
raise nx.NetworkXError(f"node {str(s)} not in graph")
if t not in G:
raise nx.NetworkXError(f"node {str(t)} not in graph")
if s == t:
raise nx.NetworkXError("source and sink are the same node")
if residual is None:
R = build_residual_network(G, capacity)
else:
R = residual
# Initialize/reset the residual network.
for u in R:
for e in R[u].values():
e["flow"] = 0
if cutoff is None:
cutoff = float("inf")
R.graph["flow_value"] = edmonds_karp_core(R, s, t, cutoff)
return R
[docs]
@nx._dispatchable(
edge_attrs={"capacity": float("inf")}, returns_graph=True, preserve_edge_attrs=True
)
def edmonds_karp(
G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None
):
"""Find a maximum single-commodity flow using the Edmonds-Karp algorithm.
This function returns the residual network resulting after computing
the maximum flow. See below for details about the conventions
NetworkX uses for defining residual networks.
This algorithm has a running time of $O(n m^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 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.
residual : NetworkX graph
Residual network on which the algorithm is to be executed. If None, a
new residual network is created. Default value: None.
value_only : bool
If True compute only the value of the maximum flow. This parameter
will be ignored by this algorithm because it is not applicable.
cutoff : integer, float
If specified, the algorithm will terminate when the flow value reaches
or exceeds the cutoff. In this case, it may be unable to immediately
determine a minimum cut. Default value: None.
Returns
-------
R : NetworkX DiGraph
Residual network after computing the maximum flow.
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
--------
:meth:`maximum_flow`
:meth:`minimum_cut`
:meth:`preflow_push`
:meth:`shortest_augmenting_path`
Notes
-----
The residual network :samp:`R` from an input graph :samp:`G` has the
same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
in :samp:`G`.
For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
in :samp:`G` or zero otherwise. If the capacity is infinite,
:samp:`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
:samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
:samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
The flow value, defined as the total flow into :samp:`t`, the sink, is
stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
:samp:`s`-:samp:`t` cut.
Examples
--------
>>> from networkx.algorithms.flow import edmonds_karp
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)
>>> R = edmonds_karp(G, "x", "y")
>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value
3.0
>>> flow_value == R.graph["flow_value"]
True
"""
R = edmonds_karp_impl(G, s, t, capacity, residual, cutoff)
R.graph["algorithm"] = "edmonds_karp"
nx._clear_cache(R)
return R
