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