|
|
""" |
|
|
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.""" |
|
|
|
|
|
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.") |
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
flow_value = 0 |
|
|
while flow_value < cutoff: |
|
|
v, pred, succ = bidirectional_bfs() |
|
|
if pred is None: |
|
|
break |
|
|
path = [v] |
|
|
|
|
|
u = v |
|
|
while u != s: |
|
|
u = pred[u] |
|
|
path.append(u) |
|
|
path.reverse() |
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=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 |
|
|
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'. |
|
|
|
|
|
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 |
|
|
|
