aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/algorithms/flow
diff options
context:
space:
mode:
authorS. Solomon Darnell2025-03-28 21:52:21 -0500
committerS. Solomon Darnell2025-03-28 21:52:21 -0500
commit4a52a71956a8d46fcb7294ac71734504bb09bcc2 (patch)
treeee3dc5af3b6313e921cd920906356f5d4febc4ed /.venv/lib/python3.12/site-packages/networkx/algorithms/flow
parentcc961e04ba734dd72309fb548a2f97d67d578813 (diff)
downloadgn-ai-master.tar.gz
two version of R2R are hereHEADmaster
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/flow')
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/__init__.py11
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/boykovkolmogorov.py370
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/capacityscaling.py407
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/dinitz_alg.py238
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/edmondskarp.py241
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/gomory_hu.py178
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/maxflow.py607
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/mincost.py356
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/networksimplex.py666
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/preflowpush.py425
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/shortestaugmentingpath.py300
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/__init__.py0
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gl1.gpickle.bz2bin0 -> 44623 bytes
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gw1.gpickle.bz2bin0 -> 42248 bytes
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/netgen-2.gpickle.bz2bin0 -> 18972 bytes
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_gomory_hu.py128
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow.py573
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow_large_graph.py156
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_mincost.py476
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_networksimplex.py387
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/wlm3.gpickle.bz2bin0 -> 88132 bytes
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/flow/utils.py189
22 files changed, 5708 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/__init__.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/__init__.py
new file mode 100644
index 00000000..c5d19abe
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/__init__.py
@@ -0,0 +1,11 @@
+from .maxflow import *
+from .mincost import *
+from .boykovkolmogorov import *
+from .dinitz_alg import *
+from .edmondskarp import *
+from .gomory_hu import *
+from .preflowpush import *
+from .shortestaugmentingpath import *
+from .capacityscaling import *
+from .networksimplex import *
+from .utils import build_flow_dict, build_residual_network
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/boykovkolmogorov.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/boykovkolmogorov.py
new file mode 100644
index 00000000..30899c6c
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/boykovkolmogorov.py
@@ -0,0 +1,370 @@
+"""
+Boykov-Kolmogorov algorithm for maximum flow problems.
+"""
+
+from collections import deque
+from operator import itemgetter
+
+import networkx as nx
+from networkx.algorithms.flow.utils import build_residual_network
+
+__all__ = ["boykov_kolmogorov"]
+
+
+@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
+def boykov_kolmogorov(
+ G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None
+):
+ r"""Find a maximum single-commodity flow using Boykov-Kolmogorov 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 worse case complexity $O(n^2 m |C|)$ for $n$ nodes, $m$
+ edges, and $|C|$ the cost of the minimum cut [1]_. This implementation
+ uses the marking heuristic defined in [2]_ which improves its running
+ time in many practical problems.
+
+ 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 boykov_kolmogorov
+
+ 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 = boykov_kolmogorov(G, "x", "y")
+ >>> flow_value = nx.maximum_flow_value(G, "x", "y")
+ >>> flow_value
+ 3.0
+ >>> flow_value == R.graph["flow_value"]
+ True
+
+ A nice feature of the Boykov-Kolmogorov algorithm is that a partition
+ of the nodes that defines a minimum cut can be easily computed based
+ on the search trees used during the algorithm. These trees are stored
+ in the graph attribute `trees` of the residual network.
+
+ >>> source_tree, target_tree = R.graph["trees"]
+ >>> partition = (set(source_tree), set(G) - set(source_tree))
+
+ Or equivalently:
+
+ >>> partition = (set(G) - set(target_tree), set(target_tree))
+
+ References
+ ----------
+ .. [1] Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison
+ of min-cut/max-flow algorithms for energy minimization in vision.
+ Pattern Analysis and Machine Intelligence, IEEE Transactions on,
+ 26(9), 1124-1137.
+ https://doi.org/10.1109/TPAMI.2004.60
+
+ .. [2] Vladimir Kolmogorov. Graph-based Algorithms for Multi-camera
+ Reconstruction Problem. PhD thesis, Cornell University, CS Department,
+ 2003. pp. 109-114.
+ https://web.archive.org/web/20170809091249/https://pub.ist.ac.at/~vnk/papers/thesis.pdf
+
+ """
+ R = boykov_kolmogorov_impl(G, s, t, capacity, residual, cutoff)
+ R.graph["algorithm"] = "boykov_kolmogorov"
+ nx._clear_cache(R)
+ return R
+
+
+def boykov_kolmogorov_impl(G, s, t, capacity, residual, cutoff):
+ 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.
+ # This is way too slow
+ # nx.set_edge_attributes(R, 0, 'flow')
+ for u in R:
+ for e in R[u].values():
+ e["flow"] = 0
+
+ # Use an arbitrary high value as infinite. It is computed
+ # when building the residual network.
+ INF = R.graph["inf"]
+
+ if cutoff is None:
+ cutoff = INF
+
+ R_succ = R.succ
+ R_pred = R.pred
+
+ def grow():
+ """Bidirectional breadth-first search for the growth stage.
+
+ Returns a connecting edge, that is and edge that connects
+ a node from the source search tree with a node from the
+ target search tree.
+ The first node in the connecting edge is always from the
+ source tree and the last node from the target tree.
+ """
+ while active:
+ u = active[0]
+ if u in source_tree:
+ this_tree = source_tree
+ other_tree = target_tree
+ neighbors = R_succ
+ else:
+ this_tree = target_tree
+ other_tree = source_tree
+ neighbors = R_pred
+ for v, attr in neighbors[u].items():
+ if attr["capacity"] - attr["flow"] > 0:
+ if v not in this_tree:
+ if v in other_tree:
+ return (u, v) if this_tree is source_tree else (v, u)
+ this_tree[v] = u
+ dist[v] = dist[u] + 1
+ timestamp[v] = timestamp[u]
+ active.append(v)
+ elif v in this_tree and _is_closer(u, v):
+ this_tree[v] = u
+ dist[v] = dist[u] + 1
+ timestamp[v] = timestamp[u]
+ _ = active.popleft()
+ return None, None
+
+ def augment(u, v):
+ """Augmentation stage.
+
+ Reconstruct path and determine its residual capacity.
+ We start from a connecting edge, which links a node
+ from the source tree to a node from the target tree.
+ The connecting edge is the output of the grow function
+ and the input of this function.
+ """
+ attr = R_succ[u][v]
+ flow = min(INF, attr["capacity"] - attr["flow"])
+ path = [u]
+ # Trace a path from u to s in source_tree.
+ w = u
+ while w != s:
+ n = w
+ w = source_tree[n]
+ attr = R_pred[n][w]
+ flow = min(flow, attr["capacity"] - attr["flow"])
+ path.append(w)
+ path.reverse()
+ # Trace a path from v to t in target_tree.
+ path.append(v)
+ w = v
+ while w != t:
+ n = w
+ w = target_tree[n]
+ attr = R_succ[n][w]
+ flow = min(flow, attr["capacity"] - attr["flow"])
+ path.append(w)
+ # Augment flow along the path and check for saturated edges.
+ it = iter(path)
+ u = next(it)
+ these_orphans = []
+ for v in it:
+ R_succ[u][v]["flow"] += flow
+ R_succ[v][u]["flow"] -= flow
+ if R_succ[u][v]["flow"] == R_succ[u][v]["capacity"]:
+ if v in source_tree:
+ source_tree[v] = None
+ these_orphans.append(v)
+ if u in target_tree:
+ target_tree[u] = None
+ these_orphans.append(u)
+ u = v
+ orphans.extend(sorted(these_orphans, key=dist.get))
+ return flow
+
+ def adopt():
+ """Adoption stage.
+
+ Reconstruct search trees by adopting or discarding orphans.
+ During augmentation stage some edges got saturated and thus
+ the source and target search trees broke down to forests, with
+ orphans as roots of some of its trees. We have to reconstruct
+ the search trees rooted to source and target before we can grow
+ them again.
+ """
+ while orphans:
+ u = orphans.popleft()
+ if u in source_tree:
+ tree = source_tree
+ neighbors = R_pred
+ else:
+ tree = target_tree
+ neighbors = R_succ
+ nbrs = ((n, attr, dist[n]) for n, attr in neighbors[u].items() if n in tree)
+ for v, attr, d in sorted(nbrs, key=itemgetter(2)):
+ if attr["capacity"] - attr["flow"] > 0:
+ if _has_valid_root(v, tree):
+ tree[u] = v
+ dist[u] = dist[v] + 1
+ timestamp[u] = time
+ break
+ else:
+ nbrs = (
+ (n, attr, dist[n]) for n, attr in neighbors[u].items() if n in tree
+ )
+ for v, attr, d in sorted(nbrs, key=itemgetter(2)):
+ if attr["capacity"] - attr["flow"] > 0:
+ if v not in active:
+ active.append(v)
+ if tree[v] == u:
+ tree[v] = None
+ orphans.appendleft(v)
+ if u in active:
+ active.remove(u)
+ del tree[u]
+
+ def _has_valid_root(n, tree):
+ path = []
+ v = n
+ while v is not None:
+ path.append(v)
+ if v in (s, t):
+ base_dist = 0
+ break
+ elif timestamp[v] == time:
+ base_dist = dist[v]
+ break
+ v = tree[v]
+ else:
+ return False
+ length = len(path)
+ for i, u in enumerate(path, 1):
+ dist[u] = base_dist + length - i
+ timestamp[u] = time
+ return True
+
+ def _is_closer(u, v):
+ return timestamp[v] <= timestamp[u] and dist[v] > dist[u] + 1
+
+ source_tree = {s: None}
+ target_tree = {t: None}
+ active = deque([s, t])
+ orphans = deque()
+ flow_value = 0
+ # data structures for the marking heuristic
+ time = 1
+ timestamp = {s: time, t: time}
+ dist = {s: 0, t: 0}
+ while flow_value < cutoff:
+ # Growth stage
+ u, v = grow()
+ if u is None:
+ break
+ time += 1
+ # Augmentation stage
+ flow_value += augment(u, v)
+ # Adoption stage
+ adopt()
+
+ if flow_value * 2 > INF:
+ raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
+
+ # Add source and target tree in a graph attribute.
+ # A partition that defines a minimum cut can be directly
+ # computed from the search trees as explained in the docstrings.
+ R.graph["trees"] = (source_tree, target_tree)
+ # Add the standard flow_value graph attribute.
+ R.graph["flow_value"] = flow_value
+ return R
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/capacityscaling.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/capacityscaling.py
new file mode 100644
index 00000000..bf68565c
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/capacityscaling.py
@@ -0,0 +1,407 @@
+"""
+Capacity scaling minimum cost flow algorithm.
+"""
+
+__all__ = ["capacity_scaling"]
+
+from itertools import chain
+from math import log
+
+import networkx as nx
+
+from ...utils import BinaryHeap, arbitrary_element, not_implemented_for
+
+
+def _detect_unboundedness(R):
+ """Detect infinite-capacity negative cycles."""
+ G = nx.DiGraph()
+ G.add_nodes_from(R)
+
+ # Value simulating infinity.
+ inf = R.graph["inf"]
+ # True infinity.
+ f_inf = float("inf")
+ for u in R:
+ for v, e in R[u].items():
+ # Compute the minimum weight of infinite-capacity (u, v) edges.
+ w = f_inf
+ for k, e in e.items():
+ if e["capacity"] == inf:
+ w = min(w, e["weight"])
+ if w != f_inf:
+ G.add_edge(u, v, weight=w)
+
+ if nx.negative_edge_cycle(G):
+ raise nx.NetworkXUnbounded(
+ "Negative cost cycle of infinite capacity found. "
+ "Min cost flow may be unbounded below."
+ )
+
+
+@not_implemented_for("undirected")
+def _build_residual_network(G, demand, capacity, weight):
+ """Build a residual network and initialize a zero flow."""
+ if sum(G.nodes[u].get(demand, 0) for u in G) != 0:
+ raise nx.NetworkXUnfeasible("Sum of the demands should be 0.")
+
+ R = nx.MultiDiGraph()
+ R.add_nodes_from(
+ (u, {"excess": -G.nodes[u].get(demand, 0), "potential": 0}) for u in G
+ )
+
+ inf = float("inf")
+ # Detect selfloops with infinite capacities and negative weights.
+ for u, v, e in nx.selfloop_edges(G, data=True):
+ if e.get(weight, 0) < 0 and e.get(capacity, inf) == inf:
+ raise nx.NetworkXUnbounded(
+ "Negative cost cycle of infinite capacity found. "
+ "Min cost flow may be unbounded below."
+ )
+
+ # Extract edges with positive capacities. Self loops excluded.
+ if G.is_multigraph():
+ edge_list = [
+ (u, v, k, e)
+ for u, v, k, e in G.edges(data=True, keys=True)
+ if u != v and e.get(capacity, inf) > 0
+ ]
+ else:
+ edge_list = [
+ (u, v, 0, e)
+ for u, v, e in G.edges(data=True)
+ if u != v and e.get(capacity, inf) > 0
+ ]
+ # Simulate infinity with the larger of the sum of absolute node imbalances
+ # the sum of finite edge capacities or any positive value if both sums are
+ # zero. This allows the infinite-capacity edges to be distinguished for
+ # unboundedness detection and directly participate in residual capacity
+ # calculation.
+ inf = (
+ max(
+ sum(abs(R.nodes[u]["excess"]) for u in R),
+ 2
+ * sum(
+ e[capacity]
+ for u, v, k, e in edge_list
+ if capacity in e and e[capacity] != inf
+ ),
+ )
+ or 1
+ )
+ for u, v, k, e in edge_list:
+ r = min(e.get(capacity, inf), inf)
+ w = e.get(weight, 0)
+ # Add both (u, v) and (v, u) into the residual network marked with the
+ # original key. (key[1] == True) indicates the (u, v) is in the
+ # original network.
+ R.add_edge(u, v, key=(k, True), capacity=r, weight=w, flow=0)
+ R.add_edge(v, u, key=(k, False), capacity=0, weight=-w, flow=0)
+
+ # Record the value simulating infinity.
+ R.graph["inf"] = inf
+
+ _detect_unboundedness(R)
+
+ return R
+
+
+def _build_flow_dict(G, R, capacity, weight):
+ """Build a flow dictionary from a residual network."""
+ inf = float("inf")
+ flow_dict = {}
+ if G.is_multigraph():
+ for u in G:
+ flow_dict[u] = {}
+ for v, es in G[u].items():
+ flow_dict[u][v] = {
+ # Always saturate negative selfloops.
+ k: (
+ 0
+ if (
+ u != v or e.get(capacity, inf) <= 0 or e.get(weight, 0) >= 0
+ )
+ else e[capacity]
+ )
+ for k, e in es.items()
+ }
+ for v, es in R[u].items():
+ if v in flow_dict[u]:
+ flow_dict[u][v].update(
+ (k[0], e["flow"]) for k, e in es.items() if e["flow"] > 0
+ )
+ else:
+ for u in G:
+ flow_dict[u] = {
+ # Always saturate negative selfloops.
+ v: (
+ 0
+ if (u != v or e.get(capacity, inf) <= 0 or e.get(weight, 0) >= 0)
+ else e[capacity]
+ )
+ for v, e in G[u].items()
+ }
+ flow_dict[u].update(
+ (v, e["flow"])
+ for v, es in R[u].items()
+ for e in es.values()
+ if e["flow"] > 0
+ )
+ return flow_dict
+
+
+@nx._dispatchable(
+ node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}
+)
+def capacity_scaling(
+ G, demand="demand", capacity="capacity", weight="weight", heap=BinaryHeap
+):
+ r"""Find a minimum cost flow satisfying all demands in digraph G.
+
+ This is a capacity scaling successive shortest augmenting path algorithm.
+
+ G is a digraph with edge costs and capacities and in which nodes
+ have demand, i.e., they want to send or receive some amount of
+ flow. A negative demand means that the node wants to send flow, a
+ positive demand means that the node want to receive flow. A flow on
+ the digraph G satisfies all demand if the net flow into each node
+ is equal to the demand of that node.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ DiGraph or MultiDiGraph on which a minimum cost flow satisfying all
+ demands is to be found.
+
+ demand : string
+ Nodes of the graph G are expected to have an attribute demand
+ that indicates how much flow a node wants to send (negative
+ demand) or receive (positive demand). Note that the sum of the
+ demands should be 0 otherwise the problem in not feasible. If
+ this attribute is not present, a node is considered to have 0
+ demand. Default value: 'demand'.
+
+ 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'.
+
+ weight : string
+ Edges of the graph G are expected to have an attribute weight
+ that indicates the cost incurred by sending one unit of flow on
+ that edge. If not present, the weight is considered to be 0.
+ Default value: 'weight'.
+
+ heap : class
+ Type of heap to be used in the algorithm. It should be a subclass of
+ :class:`MinHeap` or implement a compatible interface.
+
+ If a stock heap implementation is to be used, :class:`BinaryHeap` is
+ recommended over :class:`PairingHeap` for Python implementations without
+ optimized attribute accesses (e.g., CPython) despite a slower
+ asymptotic running time. For Python implementations with optimized
+ attribute accesses (e.g., PyPy), :class:`PairingHeap` provides better
+ performance. Default value: :class:`BinaryHeap`.
+
+ Returns
+ -------
+ flowCost : integer
+ Cost of a minimum cost flow satisfying all demands.
+
+ flowDict : dictionary
+ If G is a digraph, a dict-of-dicts keyed by nodes such that
+ flowDict[u][v] is the flow on edge (u, v).
+ If G is a MultiDiGraph, a dict-of-dicts-of-dicts keyed by nodes
+ so that flowDict[u][v][key] is the flow on edge (u, v, key).
+
+ Raises
+ ------
+ NetworkXError
+ This exception is raised if the input graph is not directed,
+ not connected.
+
+ NetworkXUnfeasible
+ This exception is raised in the following situations:
+
+ * The sum of the demands is not zero. Then, there is no
+ flow satisfying all demands.
+ * There is no flow satisfying all demand.
+
+ NetworkXUnbounded
+ This exception is raised if the digraph G has a cycle of
+ negative cost and infinite capacity. Then, the cost of a flow
+ satisfying all demands is unbounded below.
+
+ Notes
+ -----
+ This algorithm does not work if edge weights are floating-point numbers.
+
+ See also
+ --------
+ :meth:`network_simplex`
+
+ Examples
+ --------
+ A simple example of a min cost flow problem.
+
+ >>> G = nx.DiGraph()
+ >>> G.add_node("a", demand=-5)
+ >>> G.add_node("d", demand=5)
+ >>> G.add_edge("a", "b", weight=3, capacity=4)
+ >>> G.add_edge("a", "c", weight=6, capacity=10)
+ >>> G.add_edge("b", "d", weight=1, capacity=9)
+ >>> G.add_edge("c", "d", weight=2, capacity=5)
+ >>> flowCost, flowDict = nx.capacity_scaling(G)
+ >>> flowCost
+ 24
+ >>> flowDict
+ {'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
+
+ It is possible to change the name of the attributes used for the
+ algorithm.
+
+ >>> G = nx.DiGraph()
+ >>> G.add_node("p", spam=-4)
+ >>> G.add_node("q", spam=2)
+ >>> G.add_node("a", spam=-2)
+ >>> G.add_node("d", spam=-1)
+ >>> G.add_node("t", spam=2)
+ >>> G.add_node("w", spam=3)
+ >>> G.add_edge("p", "q", cost=7, vacancies=5)
+ >>> G.add_edge("p", "a", cost=1, vacancies=4)
+ >>> G.add_edge("q", "d", cost=2, vacancies=3)
+ >>> G.add_edge("t", "q", cost=1, vacancies=2)
+ >>> G.add_edge("a", "t", cost=2, vacancies=4)
+ >>> G.add_edge("d", "w", cost=3, vacancies=4)
+ >>> G.add_edge("t", "w", cost=4, vacancies=1)
+ >>> flowCost, flowDict = nx.capacity_scaling(
+ ... G, demand="spam", capacity="vacancies", weight="cost"
+ ... )
+ >>> flowCost
+ 37
+ >>> flowDict
+ {'p': {'q': 2, 'a': 2}, 'q': {'d': 1}, 'a': {'t': 4}, 'd': {'w': 2}, 't': {'q': 1, 'w': 1}, 'w': {}}
+ """
+ R = _build_residual_network(G, demand, capacity, weight)
+
+ inf = float("inf")
+ # Account cost of negative selfloops.
+ flow_cost = sum(
+ 0
+ if e.get(capacity, inf) <= 0 or e.get(weight, 0) >= 0
+ else e[capacity] * e[weight]
+ for u, v, e in nx.selfloop_edges(G, data=True)
+ )
+
+ # Determine the maximum edge capacity.
+ wmax = max(chain([-inf], (e["capacity"] for u, v, e in R.edges(data=True))))
+ if wmax == -inf:
+ # Residual network has no edges.
+ return flow_cost, _build_flow_dict(G, R, capacity, weight)
+
+ R_nodes = R.nodes
+ R_succ = R.succ
+
+ delta = 2 ** int(log(wmax, 2))
+ while delta >= 1:
+ # Saturate Δ-residual edges with negative reduced costs to achieve
+ # Δ-optimality.
+ for u in R:
+ p_u = R_nodes[u]["potential"]
+ for v, es in R_succ[u].items():
+ for k, e in es.items():
+ flow = e["capacity"] - e["flow"]
+ if e["weight"] - p_u + R_nodes[v]["potential"] < 0:
+ flow = e["capacity"] - e["flow"]
+ if flow >= delta:
+ e["flow"] += flow
+ R_succ[v][u][(k[0], not k[1])]["flow"] -= flow
+ R_nodes[u]["excess"] -= flow
+ R_nodes[v]["excess"] += flow
+ # Determine the Δ-active nodes.
+ S = set()
+ T = set()
+ S_add = S.add
+ S_remove = S.remove
+ T_add = T.add
+ T_remove = T.remove
+ for u in R:
+ excess = R_nodes[u]["excess"]
+ if excess >= delta:
+ S_add(u)
+ elif excess <= -delta:
+ T_add(u)
+ # Repeatedly augment flow from S to T along shortest paths until
+ # Δ-feasibility is achieved.
+ while S and T:
+ s = arbitrary_element(S)
+ t = None
+ # Search for a shortest path in terms of reduce costs from s to
+ # any t in T in the Δ-residual network.
+ d = {}
+ pred = {s: None}
+ h = heap()
+ h_insert = h.insert
+ h_get = h.get
+ h_insert(s, 0)
+ while h:
+ u, d_u = h.pop()
+ d[u] = d_u
+ if u in T:
+ # Path found.
+ t = u
+ break
+ p_u = R_nodes[u]["potential"]
+ for v, es in R_succ[u].items():
+ if v in d:
+ continue
+ wmin = inf
+ # Find the minimum-weighted (u, v) Δ-residual edge.
+ for k, e in es.items():
+ if e["capacity"] - e["flow"] >= delta:
+ w = e["weight"]
+ if w < wmin:
+ wmin = w
+ kmin = k
+ emin = e
+ if wmin == inf:
+ continue
+ # Update the distance label of v.
+ d_v = d_u + wmin - p_u + R_nodes[v]["potential"]
+ if h_insert(v, d_v):
+ pred[v] = (u, kmin, emin)
+ if t is not None:
+ # Augment Δ units of flow from s to t.
+ while u != s:
+ v = u
+ u, k, e = pred[v]
+ e["flow"] += delta
+ R_succ[v][u][(k[0], not k[1])]["flow"] -= delta
+ # Account node excess and deficit.
+ R_nodes[s]["excess"] -= delta
+ R_nodes[t]["excess"] += delta
+ if R_nodes[s]["excess"] < delta:
+ S_remove(s)
+ if R_nodes[t]["excess"] > -delta:
+ T_remove(t)
+ # Update node potentials.
+ d_t = d[t]
+ for u, d_u in d.items():
+ R_nodes[u]["potential"] -= d_u - d_t
+ else:
+ # Path not found.
+ S_remove(s)
+ delta //= 2
+
+ if any(R.nodes[u]["excess"] != 0 for u in R):
+ raise nx.NetworkXUnfeasible("No flow satisfying all demands.")
+
+ # Calculate the flow cost.
+ for u in R:
+ for v, es in R_succ[u].items():
+ for e in es.values():
+ flow = e["flow"]
+ if flow > 0:
+ flow_cost += flow * e["weight"]
+
+ return flow_cost, _build_flow_dict(G, R, capacity, weight)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/dinitz_alg.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/dinitz_alg.py
new file mode 100644
index 00000000..f369642a
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/dinitz_alg.py
@@ -0,0 +1,238 @@
+"""
+Dinitz' algorithm for maximum flow problems.
+"""
+
+from collections import deque
+
+import networkx as nx
+from networkx.algorithms.flow.utils import build_residual_network
+from networkx.utils import pairwise
+
+__all__ = ["dinitz"]
+
+
+@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
+def dinitz(G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None):
+ """Find a maximum single-commodity flow using Dinitz' 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^2 m)$ for $n$ nodes and $m$
+ edges [1]_.
+
+
+ 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 dinitz
+
+ 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 = dinitz(G, "x", "y")
+ >>> flow_value = nx.maximum_flow_value(G, "x", "y")
+ >>> flow_value
+ 3.0
+ >>> flow_value == R.graph["flow_value"]
+ True
+
+ References
+ ----------
+ .. [1] Dinitz' Algorithm: The Original Version and Even's Version.
+ 2006. Yefim Dinitz. In Theoretical Computer Science. Lecture
+ Notes in Computer Science. Volume 3895. pp 218-240.
+ https://doi.org/10.1007/11685654_10
+
+ """
+ R = dinitz_impl(G, s, t, capacity, residual, cutoff)
+ R.graph["algorithm"] = "dinitz"
+ nx._clear_cache(R)
+ return R
+
+
+def dinitz_impl(G, s, t, capacity, residual, cutoff):
+ 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
+
+ # Use an arbitrary high value as infinite. It is computed
+ # when building the residual network.
+ INF = R.graph["inf"]
+
+ if cutoff is None:
+ cutoff = INF
+
+ R_succ = R.succ
+ R_pred = R.pred
+
+ def breath_first_search():
+ parents = {}
+ vertex_dist = {s: 0}
+ queue = deque([(s, 0)])
+ # Record all the potential edges of shortest augmenting paths
+ while queue:
+ if t in parents:
+ break
+ u, dist = queue.popleft()
+ for v, attr in R_succ[u].items():
+ if attr["capacity"] - attr["flow"] > 0:
+ if v in parents:
+ if vertex_dist[v] == dist + 1:
+ parents[v].append(u)
+ else:
+ parents[v] = deque([u])
+ vertex_dist[v] = dist + 1
+ queue.append((v, dist + 1))
+ return parents
+
+ def depth_first_search(parents):
+ # DFS to find all the shortest augmenting paths
+ """Build a path using DFS starting from the sink"""
+ total_flow = 0
+ u = t
+ # path also functions as a stack
+ path = [u]
+ # The loop ends with no augmenting path left in the layered graph
+ while True:
+ if len(parents[u]) > 0:
+ v = parents[u][0]
+ path.append(v)
+ else:
+ path.pop()
+ if len(path) == 0:
+ break
+ v = path[-1]
+ parents[v].popleft()
+ # Augment the flow along the path found
+ if v == s:
+ flow = INF
+ for u, v in pairwise(path):
+ flow = min(flow, R_pred[u][v]["capacity"] - R_pred[u][v]["flow"])
+ for u, v in pairwise(reversed(path)):
+ R_pred[v][u]["flow"] += flow
+ R_pred[u][v]["flow"] -= flow
+ # Find the proper node to continue the search
+ if R_pred[v][u]["capacity"] - R_pred[v][u]["flow"] == 0:
+ parents[v].popleft()
+ while path[-1] != v:
+ path.pop()
+ total_flow += flow
+ v = path[-1]
+ u = v
+ return total_flow
+
+ flow_value = 0
+ while flow_value < cutoff:
+ parents = breath_first_search()
+ if t not in parents:
+ break
+ this_flow = depth_first_search(parents)
+ if this_flow * 2 > INF:
+ raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
+ flow_value += this_flow
+
+ R.graph["flow_value"] = flow_value
+ return R
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/edmondskarp.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/edmondskarp.py
new file mode 100644
index 00000000..50063268
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/edmondskarp.py
@@ -0,0 +1,241 @@
+"""
+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
+
+
+@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
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/gomory_hu.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/gomory_hu.py
new file mode 100644
index 00000000..69913da9
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/gomory_hu.py
@@ -0,0 +1,178 @@
+"""
+Gomory-Hu tree of undirected Graphs.
+"""
+
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+from .edmondskarp import edmonds_karp
+from .utils import build_residual_network
+
+default_flow_func = edmonds_karp
+
+__all__ = ["gomory_hu_tree"]
+
+
+@not_implemented_for("directed")
+@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
+def gomory_hu_tree(G, capacity="capacity", flow_func=None):
+ r"""Returns the Gomory-Hu tree of an undirected graph G.
+
+ A Gomory-Hu tree of an undirected graph with capacities is a
+ weighted tree that represents the minimum s-t cuts for all s-t
+ pairs in the graph.
+
+ It only requires `n-1` minimum cut computations instead of the
+ obvious `n(n-1)/2`. The tree represents all s-t cuts as the
+ minimum cut value among any pair of nodes is the minimum edge
+ weight in the shortest path between the two nodes in the
+ Gomory-Hu tree.
+
+ The Gomory-Hu tree also has the property that removing the
+ edge with the minimum weight in the shortest path between
+ any two nodes leaves two connected components that form
+ a partition of the nodes in G that defines the minimum s-t
+ cut.
+
+ See Examples section below for details.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ Undirected graph
+
+ 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'.
+
+ flow_func : function
+ Function to perform the underlying flow computations. Default value
+ :func:`edmonds_karp`. This function performs better in sparse graphs
+ with right tailed degree distributions.
+ :func:`shortest_augmenting_path` will perform better in denser
+ graphs.
+
+ Returns
+ -------
+ Tree : NetworkX graph
+ A NetworkX graph representing the Gomory-Hu tree of the input graph.
+
+ Raises
+ ------
+ NetworkXNotImplemented
+ Raised if the input graph is directed.
+
+ NetworkXError
+ Raised if the input graph is an empty Graph.
+
+ Examples
+ --------
+ >>> G = nx.karate_club_graph()
+ >>> nx.set_edge_attributes(G, 1, "capacity")
+ >>> T = nx.gomory_hu_tree(G)
+ >>> # The value of the minimum cut between any pair
+ ... # of nodes in G is the minimum edge weight in the
+ ... # shortest path between the two nodes in the
+ ... # Gomory-Hu tree.
+ ... def minimum_edge_weight_in_shortest_path(T, u, v):
+ ... path = nx.shortest_path(T, u, v, weight="weight")
+ ... return min((T[u][v]["weight"], (u, v)) for (u, v) in zip(path, path[1:]))
+ >>> u, v = 0, 33
+ >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
+ >>> cut_value
+ 10
+ >>> nx.minimum_cut_value(G, u, v)
+ 10
+ >>> # The Gomory-Hu tree also has the property that removing the
+ ... # edge with the minimum weight in the shortest path between
+ ... # any two nodes leaves two connected components that form
+ ... # a partition of the nodes in G that defines the minimum s-t
+ ... # cut.
+ ... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
+ >>> T.remove_edge(*edge)
+ >>> U, V = list(nx.connected_components(T))
+ >>> # Thus U and V form a partition that defines a minimum cut
+ ... # between u and v in G. You can compute the edge cut set,
+ ... # that is, the set of edges that if removed from G will
+ ... # disconnect u from v in G, with this information:
+ ... cutset = set()
+ >>> for x, nbrs in ((n, G[n]) for n in U):
+ ... cutset.update((x, y) for y in nbrs if y in V)
+ >>> # Because we have set the capacities of all edges to 1
+ ... # the cutset contains ten edges
+ ... len(cutset)
+ 10
+ >>> # You can use any maximum flow algorithm for the underlying
+ ... # flow computations using the argument flow_func
+ ... from networkx.algorithms import flow
+ >>> T = nx.gomory_hu_tree(G, flow_func=flow.boykov_kolmogorov)
+ >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
+ >>> cut_value
+ 10
+ >>> nx.minimum_cut_value(G, u, v, flow_func=flow.boykov_kolmogorov)
+ 10
+
+ Notes
+ -----
+ This implementation is based on Gusfield approach [1]_ to compute
+ Gomory-Hu trees, which does not require node contractions and has
+ the same computational complexity than the original method.
+
+ See also
+ --------
+ :func:`minimum_cut`
+ :func:`maximum_flow`
+
+ References
+ ----------
+ .. [1] Gusfield D: Very simple methods for all pairs network flow analysis.
+ SIAM J Comput 19(1):143-155, 1990.
+
+ """
+ if flow_func is None:
+ flow_func = default_flow_func
+
+ if len(G) == 0: # empty graph
+ msg = "Empty Graph does not have a Gomory-Hu tree representation"
+ raise nx.NetworkXError(msg)
+
+ # Start the tree as a star graph with an arbitrary node at the center
+ tree = {}
+ labels = {}
+ iter_nodes = iter(G)
+ root = next(iter_nodes)
+ for n in iter_nodes:
+ tree[n] = root
+
+ # Reuse residual network
+ R = build_residual_network(G, capacity)
+
+ # For all the leaves in the star graph tree (that is n-1 nodes).
+ for source in tree:
+ # Find neighbor in the tree
+ target = tree[source]
+ # compute minimum cut
+ cut_value, partition = nx.minimum_cut(
+ G, source, target, capacity=capacity, flow_func=flow_func, residual=R
+ )
+ labels[(source, target)] = cut_value
+ # Update the tree
+ # Source will always be in partition[0] and target in partition[1]
+ for node in partition[0]:
+ if node != source and node in tree and tree[node] == target:
+ tree[node] = source
+ labels[node, source] = labels.get((node, target), cut_value)
+ #
+ if target != root and tree[target] in partition[0]:
+ labels[source, tree[target]] = labels[target, tree[target]]
+ labels[target, source] = cut_value
+ tree[source] = tree[target]
+ tree[target] = source
+
+ # Build the tree
+ T = nx.Graph()
+ T.add_nodes_from(G)
+ T.add_weighted_edges_from(((u, v, labels[u, v]) for u, v in tree.items()))
+ return T
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/maxflow.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/maxflow.py
new file mode 100644
index 00000000..7993d87b
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/maxflow.py
@@ -0,0 +1,607 @@
+"""
+Maximum flow (and minimum cut) algorithms on capacitated graphs.
+"""
+
+import networkx as nx
+
+from .boykovkolmogorov import boykov_kolmogorov
+from .dinitz_alg import dinitz
+from .edmondskarp import edmonds_karp
+from .preflowpush import preflow_push
+from .shortestaugmentingpath import shortest_augmenting_path
+from .utils import build_flow_dict
+
+# Define the default flow function for computing maximum flow.
+default_flow_func = preflow_push
+
+__all__ = ["maximum_flow", "maximum_flow_value", "minimum_cut", "minimum_cut_value"]
+
+
+@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
+def maximum_flow(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
+ """Find a maximum single-commodity flow.
+
+ Parameters
+ ----------
+ flowG : 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'.
+
+ flow_func : function
+ 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 (:meth:`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.
+
+ kwargs : Any other keyword parameter is passed to the function that
+ computes the maximum flow.
+
+ Returns
+ -------
+ flow_value : integer, float
+ Value of the maximum flow, i.e., net outflow from the source.
+
+ flow_dict : dict
+ A dictionary containing the value of the flow that went through
+ each edge.
+
+ 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_value`
+ :meth:`minimum_cut`
+ :meth:`minimum_cut_value`
+ :meth:`edmonds_karp`
+ :meth:`preflow_push`
+ :meth:`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 :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']`. 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.
+
+ Specific algorithms may store extra data in :samp:`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 returns both the value of the maximum flow and a
+ dictionary with all flows.
+
+ >>> flow_value, flow_dict = nx.maximum_flow(G, "x", "y")
+ >>> flow_value
+ 3.0
+ >>> print(flow_dict["x"]["b"])
+ 1.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(G, "x", "y", flow_func=shortest_augmenting_path)[
+ ... 0
+ ... ]
+ True
+
+ """
+ if flow_func is None:
+ if kwargs:
+ raise nx.NetworkXError(
+ "You have to explicitly set a flow_func if"
+ " you need to pass parameters via kwargs."
+ )
+ flow_func = default_flow_func
+
+ if not callable(flow_func):
+ raise nx.NetworkXError("flow_func has to be callable.")
+
+ R = flow_func(flowG, _s, _t, capacity=capacity, value_only=False, **kwargs)
+ flow_dict = build_flow_dict(flowG, R)
+
+ return (R.graph["flow_value"], flow_dict)
+
+
+@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
+def maximum_flow_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
+ """Find the value of maximum single-commodity flow.
+
+ Parameters
+ ----------
+ flowG : 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'.
+
+ flow_func : function
+ 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 (:meth:`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.
+
+ kwargs : Any other keyword parameter is passed to the function that
+ computes the maximum flow.
+
+ Returns
+ -------
+ flow_value : integer, 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
+ --------
+ :meth:`maximum_flow`
+ :meth:`minimum_cut`
+ :meth:`minimum_cut_value`
+ :meth:`edmonds_karp`
+ :meth:`preflow_push`
+ :meth:`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 :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']`. 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.
+
+ Specific algorithms may store extra data in :samp:`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
+
+ """
+ if flow_func is None:
+ if kwargs:
+ raise nx.NetworkXError(
+ "You have to explicitly set a flow_func if"
+ " you need to pass parameters via kwargs."
+ )
+ flow_func = default_flow_func
+
+ if not callable(flow_func):
+ raise nx.NetworkXError("flow_func has to be callable.")
+
+ R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
+
+ return R.graph["flow_value"]
+
+
+@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
+def minimum_cut(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
+ """Compute the value and the node partition of a minimum (s, t)-cut.
+
+ Use the max-flow min-cut theorem, i.e., the capacity of a minimum
+ capacity cut is equal to the flow value of a maximum flow.
+
+ Parameters
+ ----------
+ flowG : 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'.
+
+ flow_func : function
+ 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 (:meth:`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.
+
+ kwargs : Any other keyword parameter is passed to the function that
+ computes the maximum flow.
+
+ Returns
+ -------
+ cut_value : integer, float
+ Value of the minimum cut.
+
+ partition : pair of node sets
+ A partitioning of the nodes that defines a minimum cut.
+
+ Raises
+ ------
+ NetworkXUnbounded
+ If the graph has a path of infinite capacity, all cuts have
+ infinite capacity and the function raises a NetworkXError.
+
+ See also
+ --------
+ :meth:`maximum_flow`
+ :meth:`maximum_flow_value`
+ :meth:`minimum_cut_value`
+ :meth:`edmonds_karp`
+ :meth:`preflow_push`
+ :meth:`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 :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']`. 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.
+
+ Specific algorithms may store extra data in :samp:`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)
+
+ minimum_cut computes both the value of the
+ minimum cut and the node partition:
+
+ >>> cut_value, partition = nx.minimum_cut(G, "x", "y")
+ >>> reachable, non_reachable = partition
+
+ 'partition' here is a tuple with the two sets of nodes that define
+ the minimum cut. You can compute the cut set of edges that induce
+ the minimum cut as follows:
+
+ >>> cutset = set()
+ >>> for u, nbrs in ((n, G[n]) for n in reachable):
+ ... cutset.update((u, v) for v in nbrs if v in non_reachable)
+ >>> print(sorted(cutset))
+ [('c', 'y'), ('x', 'b')]
+ >>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset)
+ True
+
+ You can also use alternative algorithms for computing the
+ minimum cut by using the flow_func parameter.
+
+ >>> from networkx.algorithms.flow import shortest_augmenting_path
+ >>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0]
+ True
+
+ """
+ if flow_func is None:
+ if kwargs:
+ raise nx.NetworkXError(
+ "You have to explicitly set a flow_func if"
+ " you need to pass parameters via kwargs."
+ )
+ flow_func = default_flow_func
+
+ if not callable(flow_func):
+ raise nx.NetworkXError("flow_func has to be callable.")
+
+ if kwargs.get("cutoff") is not None and flow_func is preflow_push:
+ raise nx.NetworkXError("cutoff should not be specified.")
+
+ R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
+ # Remove saturated edges from the residual network
+ cutset = [(u, v, d) for u, v, d in R.edges(data=True) if d["flow"] == d["capacity"]]
+ R.remove_edges_from(cutset)
+
+ # Then, reachable and non reachable nodes from source in the
+ # residual network form the node partition that defines
+ # the minimum cut.
+ non_reachable = set(dict(nx.shortest_path_length(R, target=_t)))
+ partition = (set(flowG) - non_reachable, non_reachable)
+ # Finally add again cutset edges to the residual network to make
+ # sure that it is reusable.
+ R.add_edges_from(cutset)
+ return (R.graph["flow_value"], partition)
+
+
+@nx._dispatchable(graphs="flowG", edge_attrs={"capacity": float("inf")})
+def minimum_cut_value(flowG, _s, _t, capacity="capacity", flow_func=None, **kwargs):
+ """Compute the value of a minimum (s, t)-cut.
+
+ Use the max-flow min-cut theorem, i.e., the capacity of a minimum
+ capacity cut is equal to the flow value of a maximum flow.
+
+ Parameters
+ ----------
+ flowG : 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'.
+
+ flow_func : function
+ 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 (:meth:`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.
+
+ kwargs : Any other keyword parameter is passed to the function that
+ computes the maximum flow.
+
+ Returns
+ -------
+ cut_value : integer, float
+ Value of the minimum cut.
+
+ Raises
+ ------
+ NetworkXUnbounded
+ If the graph has a path of infinite capacity, all cuts have
+ infinite capacity and the function raises a NetworkXError.
+
+ See also
+ --------
+ :meth:`maximum_flow`
+ :meth:`maximum_flow_value`
+ :meth:`minimum_cut`
+ :meth:`edmonds_karp`
+ :meth:`preflow_push`
+ :meth:`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 :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']`. 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.
+
+ Specific algorithms may store extra data in :samp:`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)
+
+ minimum_cut_value computes only the value of the
+ minimum cut:
+
+ >>> cut_value = nx.minimum_cut_value(G, "x", "y")
+ >>> cut_value
+ 3.0
+
+ You can also use alternative algorithms for computing the
+ minimum cut by using the flow_func parameter.
+
+ >>> from networkx.algorithms.flow import shortest_augmenting_path
+ >>> cut_value == nx.minimum_cut_value(
+ ... G, "x", "y", flow_func=shortest_augmenting_path
+ ... )
+ True
+
+ """
+ if flow_func is None:
+ if kwargs:
+ raise nx.NetworkXError(
+ "You have to explicitly set a flow_func if"
+ " you need to pass parameters via kwargs."
+ )
+ flow_func = default_flow_func
+
+ if not callable(flow_func):
+ raise nx.NetworkXError("flow_func has to be callable.")
+
+ if kwargs.get("cutoff") is not None and flow_func is preflow_push:
+ raise nx.NetworkXError("cutoff should not be specified.")
+
+ R = flow_func(flowG, _s, _t, capacity=capacity, value_only=True, **kwargs)
+
+ return R.graph["flow_value"]
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/mincost.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/mincost.py
new file mode 100644
index 00000000..2f9390d7
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/mincost.py
@@ -0,0 +1,356 @@
+"""
+Minimum cost flow algorithms on directed connected graphs.
+"""
+
+__all__ = ["min_cost_flow_cost", "min_cost_flow", "cost_of_flow", "max_flow_min_cost"]
+
+import networkx as nx
+
+
+@nx._dispatchable(
+ node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}
+)
+def min_cost_flow_cost(G, demand="demand", capacity="capacity", weight="weight"):
+ r"""Find the cost of a minimum cost flow satisfying all demands in digraph G.
+
+ G is a digraph with edge costs and capacities and in which nodes
+ have demand, i.e., they want to send or receive some amount of
+ flow. A negative demand means that the node wants to send flow, a
+ positive demand means that the node want to receive flow. A flow on
+ the digraph G satisfies all demand if the net flow into each node
+ is equal to the demand of that node.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ DiGraph on which a minimum cost flow satisfying all demands is
+ to be found.
+
+ demand : string
+ Nodes of the graph G are expected to have an attribute demand
+ that indicates how much flow a node wants to send (negative
+ demand) or receive (positive demand). Note that the sum of the
+ demands should be 0 otherwise the problem in not feasible. If
+ this attribute is not present, a node is considered to have 0
+ demand. Default value: 'demand'.
+
+ 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'.
+
+ weight : string
+ Edges of the graph G are expected to have an attribute weight
+ that indicates the cost incurred by sending one unit of flow on
+ that edge. If not present, the weight is considered to be 0.
+ Default value: 'weight'.
+
+ Returns
+ -------
+ flowCost : integer, float
+ Cost of a minimum cost flow satisfying all demands.
+
+ Raises
+ ------
+ NetworkXError
+ This exception is raised if the input graph is not directed or
+ not connected.
+
+ NetworkXUnfeasible
+ This exception is raised in the following situations:
+
+ * The sum of the demands is not zero. Then, there is no
+ flow satisfying all demands.
+ * There is no flow satisfying all demand.
+
+ NetworkXUnbounded
+ This exception is raised if the digraph G has a cycle of
+ negative cost and infinite capacity. Then, the cost of a flow
+ satisfying all demands is unbounded below.
+
+ See also
+ --------
+ cost_of_flow, max_flow_min_cost, min_cost_flow, network_simplex
+
+ Notes
+ -----
+ This algorithm is not guaranteed to work if edge weights or demands
+ are floating point numbers (overflows and roundoff errors can
+ cause problems). As a workaround you can use integer numbers by
+ multiplying the relevant edge attributes by a convenient
+ constant factor (eg 100).
+
+ Examples
+ --------
+ A simple example of a min cost flow problem.
+
+ >>> G = nx.DiGraph()
+ >>> G.add_node("a", demand=-5)
+ >>> G.add_node("d", demand=5)
+ >>> G.add_edge("a", "b", weight=3, capacity=4)
+ >>> G.add_edge("a", "c", weight=6, capacity=10)
+ >>> G.add_edge("b", "d", weight=1, capacity=9)
+ >>> G.add_edge("c", "d", weight=2, capacity=5)
+ >>> flowCost = nx.min_cost_flow_cost(G)
+ >>> flowCost
+ 24
+ """
+ return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[0]
+
+
+@nx._dispatchable(
+ node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}
+)
+def min_cost_flow(G, demand="demand", capacity="capacity", weight="weight"):
+ r"""Returns a minimum cost flow satisfying all demands in digraph G.
+
+ G is a digraph with edge costs and capacities and in which nodes
+ have demand, i.e., they want to send or receive some amount of
+ flow. A negative demand means that the node wants to send flow, a
+ positive demand means that the node want to receive flow. A flow on
+ the digraph G satisfies all demand if the net flow into each node
+ is equal to the demand of that node.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ DiGraph on which a minimum cost flow satisfying all demands is
+ to be found.
+
+ demand : string
+ Nodes of the graph G are expected to have an attribute demand
+ that indicates how much flow a node wants to send (negative
+ demand) or receive (positive demand). Note that the sum of the
+ demands should be 0 otherwise the problem in not feasible. If
+ this attribute is not present, a node is considered to have 0
+ demand. Default value: 'demand'.
+
+ 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'.
+
+ weight : string
+ Edges of the graph G are expected to have an attribute weight
+ that indicates the cost incurred by sending one unit of flow on
+ that edge. If not present, the weight is considered to be 0.
+ Default value: 'weight'.
+
+ Returns
+ -------
+ flowDict : dictionary
+ Dictionary of dictionaries keyed by nodes such that
+ flowDict[u][v] is the flow edge (u, v).
+
+ Raises
+ ------
+ NetworkXError
+ This exception is raised if the input graph is not directed or
+ not connected.
+
+ NetworkXUnfeasible
+ This exception is raised in the following situations:
+
+ * The sum of the demands is not zero. Then, there is no
+ flow satisfying all demands.
+ * There is no flow satisfying all demand.
+
+ NetworkXUnbounded
+ This exception is raised if the digraph G has a cycle of
+ negative cost and infinite capacity. Then, the cost of a flow
+ satisfying all demands is unbounded below.
+
+ See also
+ --------
+ cost_of_flow, max_flow_min_cost, min_cost_flow_cost, network_simplex
+
+ Notes
+ -----
+ This algorithm is not guaranteed to work if edge weights or demands
+ are floating point numbers (overflows and roundoff errors can
+ cause problems). As a workaround you can use integer numbers by
+ multiplying the relevant edge attributes by a convenient
+ constant factor (eg 100).
+
+ Examples
+ --------
+ A simple example of a min cost flow problem.
+
+ >>> G = nx.DiGraph()
+ >>> G.add_node("a", demand=-5)
+ >>> G.add_node("d", demand=5)
+ >>> G.add_edge("a", "b", weight=3, capacity=4)
+ >>> G.add_edge("a", "c", weight=6, capacity=10)
+ >>> G.add_edge("b", "d", weight=1, capacity=9)
+ >>> G.add_edge("c", "d", weight=2, capacity=5)
+ >>> flowDict = nx.min_cost_flow(G)
+ >>> flowDict
+ {'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
+ """
+ return nx.network_simplex(G, demand=demand, capacity=capacity, weight=weight)[1]
+
+
+@nx._dispatchable(edge_attrs={"weight": 0})
+def cost_of_flow(G, flowDict, weight="weight"):
+ """Compute the cost of the flow given by flowDict on graph G.
+
+ Note that this function does not check for the validity of the
+ flow flowDict. This function will fail if the graph G and the
+ flow don't have the same edge set.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ DiGraph on which a minimum cost flow satisfying all demands is
+ to be found.
+
+ weight : string
+ Edges of the graph G are expected to have an attribute weight
+ that indicates the cost incurred by sending one unit of flow on
+ that edge. If not present, the weight is considered to be 0.
+ Default value: 'weight'.
+
+ flowDict : dictionary
+ Dictionary of dictionaries keyed by nodes such that
+ flowDict[u][v] is the flow edge (u, v).
+
+ Returns
+ -------
+ cost : Integer, float
+ The total cost of the flow. This is given by the sum over all
+ edges of the product of the edge's flow and the edge's weight.
+
+ See also
+ --------
+ max_flow_min_cost, min_cost_flow, min_cost_flow_cost, network_simplex
+
+ Notes
+ -----
+ This algorithm is not guaranteed to work if edge weights or demands
+ are floating point numbers (overflows and roundoff errors can
+ cause problems). As a workaround you can use integer numbers by
+ multiplying the relevant edge attributes by a convenient
+ constant factor (eg 100).
+
+ Examples
+ --------
+ >>> G = nx.DiGraph()
+ >>> G.add_node("a", demand=-5)
+ >>> G.add_node("d", demand=5)
+ >>> G.add_edge("a", "b", weight=3, capacity=4)
+ >>> G.add_edge("a", "c", weight=6, capacity=10)
+ >>> G.add_edge("b", "d", weight=1, capacity=9)
+ >>> G.add_edge("c", "d", weight=2, capacity=5)
+ >>> flowDict = nx.min_cost_flow(G)
+ >>> flowDict
+ {'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
+ >>> nx.cost_of_flow(G, flowDict)
+ 24
+ """
+ return sum((flowDict[u][v] * d.get(weight, 0) for u, v, d in G.edges(data=True)))
+
+
+@nx._dispatchable(edge_attrs={"capacity": float("inf"), "weight": 0})
+def max_flow_min_cost(G, s, t, capacity="capacity", weight="weight"):
+ """Returns a maximum (s, t)-flow of minimum cost.
+
+ G is a digraph with edge costs and capacities. There is a source
+ node s and a sink node t. This function finds a maximum flow from
+ s to t whose total cost is minimized.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ DiGraph on which a minimum cost flow satisfying all demands is
+ to be found.
+
+ s: node label
+ Source of the flow.
+
+ t: node label
+ Destination of 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'.
+
+ weight: string
+ Edges of the graph G are expected to have an attribute weight
+ that indicates the cost incurred by sending one unit of flow on
+ that edge. If not present, the weight is considered to be 0.
+ Default value: 'weight'.
+
+ Returns
+ -------
+ flowDict: dictionary
+ Dictionary of dictionaries keyed by nodes such that
+ flowDict[u][v] is the flow edge (u, v).
+
+ Raises
+ ------
+ NetworkXError
+ This exception is raised if the input graph is not directed or
+ not connected.
+
+ NetworkXUnbounded
+ This exception is raised if there is an infinite capacity path
+ from s to t in G. In this case there is no maximum flow. This
+ exception is also raised if the digraph G has a cycle of
+ negative cost and infinite capacity. Then, the cost of a flow
+ is unbounded below.
+
+ See also
+ --------
+ cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex
+
+ Notes
+ -----
+ This algorithm is not guaranteed to work if edge weights or demands
+ are floating point numbers (overflows and roundoff errors can
+ cause problems). As a workaround you can use integer numbers by
+ multiplying the relevant edge attributes by a convenient
+ constant factor (eg 100).
+
+ Examples
+ --------
+ >>> G = nx.DiGraph()
+ >>> G.add_edges_from(
+ ... [
+ ... (1, 2, {"capacity": 12, "weight": 4}),
+ ... (1, 3, {"capacity": 20, "weight": 6}),
+ ... (2, 3, {"capacity": 6, "weight": -3}),
+ ... (2, 6, {"capacity": 14, "weight": 1}),
+ ... (3, 4, {"weight": 9}),
+ ... (3, 5, {"capacity": 10, "weight": 5}),
+ ... (4, 2, {"capacity": 19, "weight": 13}),
+ ... (4, 5, {"capacity": 4, "weight": 0}),
+ ... (5, 7, {"capacity": 28, "weight": 2}),
+ ... (6, 5, {"capacity": 11, "weight": 1}),
+ ... (6, 7, {"weight": 8}),
+ ... (7, 4, {"capacity": 6, "weight": 6}),
+ ... ]
+ ... )
+ >>> mincostFlow = nx.max_flow_min_cost(G, 1, 7)
+ >>> mincost = nx.cost_of_flow(G, mincostFlow)
+ >>> mincost
+ 373
+ >>> from networkx.algorithms.flow import maximum_flow
+ >>> maxFlow = maximum_flow(G, 1, 7)[1]
+ >>> nx.cost_of_flow(G, maxFlow) >= mincost
+ True
+ >>> mincostFlowValue = sum((mincostFlow[u][7] for u in G.predecessors(7))) - sum(
+ ... (mincostFlow[7][v] for v in G.successors(7))
+ ... )
+ >>> mincostFlowValue == nx.maximum_flow_value(G, 1, 7)
+ True
+
+ """
+ maxFlow = nx.maximum_flow_value(G, s, t, capacity=capacity)
+ H = nx.DiGraph(G)
+ H.add_node(s, demand=-maxFlow)
+ H.add_node(t, demand=maxFlow)
+ return min_cost_flow(H, capacity=capacity, weight=weight)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/networksimplex.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/networksimplex.py
new file mode 100644
index 00000000..a9822d96
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/networksimplex.py
@@ -0,0 +1,666 @@
+"""
+Minimum cost flow algorithms on directed connected graphs.
+"""
+
+__all__ = ["network_simplex"]
+
+from itertools import chain, islice, repeat
+from math import ceil, sqrt
+
+import networkx as nx
+from networkx.utils import not_implemented_for
+
+
+class _DataEssentialsAndFunctions:
+ def __init__(
+ self, G, multigraph, demand="demand", capacity="capacity", weight="weight"
+ ):
+ # Number all nodes and edges and hereafter reference them using ONLY their numbers
+ self.node_list = list(G) # nodes
+ self.node_indices = {u: i for i, u in enumerate(self.node_list)} # node indices
+ self.node_demands = [
+ G.nodes[u].get(demand, 0) for u in self.node_list
+ ] # node demands
+
+ self.edge_sources = [] # edge sources
+ self.edge_targets = [] # edge targets
+ if multigraph:
+ self.edge_keys = [] # edge keys
+ self.edge_indices = {} # edge indices
+ self.edge_capacities = [] # edge capacities
+ self.edge_weights = [] # edge weights
+
+ if not multigraph:
+ edges = G.edges(data=True)
+ else:
+ edges = G.edges(data=True, keys=True)
+
+ inf = float("inf")
+ edges = (e for e in edges if e[0] != e[1] and e[-1].get(capacity, inf) != 0)
+ for i, e in enumerate(edges):
+ self.edge_sources.append(self.node_indices[e[0]])
+ self.edge_targets.append(self.node_indices[e[1]])
+ if multigraph:
+ self.edge_keys.append(e[2])
+ self.edge_indices[e[:-1]] = i
+ self.edge_capacities.append(e[-1].get(capacity, inf))
+ self.edge_weights.append(e[-1].get(weight, 0))
+
+ # spanning tree specific data to be initialized
+
+ self.edge_count = None # number of edges
+ self.edge_flow = None # edge flows
+ self.node_potentials = None # node potentials
+ self.parent = None # parent nodes
+ self.parent_edge = None # edges to parents
+ self.subtree_size = None # subtree sizes
+ self.next_node_dft = None # next nodes in depth-first thread
+ self.prev_node_dft = None # previous nodes in depth-first thread
+ self.last_descendent_dft = None # last descendants in depth-first thread
+ self._spanning_tree_initialized = (
+ False # False until initialize_spanning_tree() is called
+ )
+
+ def initialize_spanning_tree(self, n, faux_inf):
+ self.edge_count = len(self.edge_indices) # number of edges
+ self.edge_flow = list(
+ chain(repeat(0, self.edge_count), (abs(d) for d in self.node_demands))
+ ) # edge flows
+ self.node_potentials = [
+ faux_inf if d <= 0 else -faux_inf for d in self.node_demands
+ ] # node potentials
+ self.parent = list(chain(repeat(-1, n), [None])) # parent nodes
+ self.parent_edge = list(
+ range(self.edge_count, self.edge_count + n)
+ ) # edges to parents
+ self.subtree_size = list(chain(repeat(1, n), [n + 1])) # subtree sizes
+ self.next_node_dft = list(
+ chain(range(1, n), [-1, 0])
+ ) # next nodes in depth-first thread
+ self.prev_node_dft = list(range(-1, n)) # previous nodes in depth-first thread
+ self.last_descendent_dft = list(
+ chain(range(n), [n - 1])
+ ) # last descendants in depth-first thread
+ self._spanning_tree_initialized = True # True only if all the assignments pass
+
+ def find_apex(self, p, q):
+ """
+ Find the lowest common ancestor of nodes p and q in the spanning tree.
+ """
+ size_p = self.subtree_size[p]
+ size_q = self.subtree_size[q]
+ while True:
+ while size_p < size_q:
+ p = self.parent[p]
+ size_p = self.subtree_size[p]
+ while size_p > size_q:
+ q = self.parent[q]
+ size_q = self.subtree_size[q]
+ if size_p == size_q:
+ if p != q:
+ p = self.parent[p]
+ size_p = self.subtree_size[p]
+ q = self.parent[q]
+ size_q = self.subtree_size[q]
+ else:
+ return p
+
+ def trace_path(self, p, w):
+ """
+ Returns the nodes and edges on the path from node p to its ancestor w.
+ """
+ Wn = [p]
+ We = []
+ while p != w:
+ We.append(self.parent_edge[p])
+ p = self.parent[p]
+ Wn.append(p)
+ return Wn, We
+
+ def find_cycle(self, i, p, q):
+ """
+ Returns the nodes and edges on the cycle containing edge i == (p, q)
+ when the latter is added to the spanning tree.
+
+ The cycle is oriented in the direction from p to q.
+ """
+ w = self.find_apex(p, q)
+ Wn, We = self.trace_path(p, w)
+ Wn.reverse()
+ We.reverse()
+ if We != [i]:
+ We.append(i)
+ WnR, WeR = self.trace_path(q, w)
+ del WnR[-1]
+ Wn += WnR
+ We += WeR
+ return Wn, We
+
+ def augment_flow(self, Wn, We, f):
+ """
+ Augment f units of flow along a cycle represented by Wn and We.
+ """
+ for i, p in zip(We, Wn):
+ if self.edge_sources[i] == p:
+ self.edge_flow[i] += f
+ else:
+ self.edge_flow[i] -= f
+
+ def trace_subtree(self, p):
+ """
+ Yield the nodes in the subtree rooted at a node p.
+ """
+ yield p
+ l = self.last_descendent_dft[p]
+ while p != l:
+ p = self.next_node_dft[p]
+ yield p
+
+ def remove_edge(self, s, t):
+ """
+ Remove an edge (s, t) where parent[t] == s from the spanning tree.
+ """
+ size_t = self.subtree_size[t]
+ prev_t = self.prev_node_dft[t]
+ last_t = self.last_descendent_dft[t]
+ next_last_t = self.next_node_dft[last_t]
+ # Remove (s, t).
+ self.parent[t] = None
+ self.parent_edge[t] = None
+ # Remove the subtree rooted at t from the depth-first thread.
+ self.next_node_dft[prev_t] = next_last_t
+ self.prev_node_dft[next_last_t] = prev_t
+ self.next_node_dft[last_t] = t
+ self.prev_node_dft[t] = last_t
+ # Update the subtree sizes and last descendants of the (old) ancestors
+ # of t.
+ while s is not None:
+ self.subtree_size[s] -= size_t
+ if self.last_descendent_dft[s] == last_t:
+ self.last_descendent_dft[s] = prev_t
+ s = self.parent[s]
+
+ def make_root(self, q):
+ """
+ Make a node q the root of its containing subtree.
+ """
+ ancestors = []
+ while q is not None:
+ ancestors.append(q)
+ q = self.parent[q]
+ ancestors.reverse()
+ for p, q in zip(ancestors, islice(ancestors, 1, None)):
+ size_p = self.subtree_size[p]
+ last_p = self.last_descendent_dft[p]
+ prev_q = self.prev_node_dft[q]
+ last_q = self.last_descendent_dft[q]
+ next_last_q = self.next_node_dft[last_q]
+ # Make p a child of q.
+ self.parent[p] = q
+ self.parent[q] = None
+ self.parent_edge[p] = self.parent_edge[q]
+ self.parent_edge[q] = None
+ self.subtree_size[p] = size_p - self.subtree_size[q]
+ self.subtree_size[q] = size_p
+ # Remove the subtree rooted at q from the depth-first thread.
+ self.next_node_dft[prev_q] = next_last_q
+ self.prev_node_dft[next_last_q] = prev_q
+ self.next_node_dft[last_q] = q
+ self.prev_node_dft[q] = last_q
+ if last_p == last_q:
+ self.last_descendent_dft[p] = prev_q
+ last_p = prev_q
+ # Add the remaining parts of the subtree rooted at p as a subtree
+ # of q in the depth-first thread.
+ self.prev_node_dft[p] = last_q
+ self.next_node_dft[last_q] = p
+ self.next_node_dft[last_p] = q
+ self.prev_node_dft[q] = last_p
+ self.last_descendent_dft[q] = last_p
+
+ def add_edge(self, i, p, q):
+ """
+ Add an edge (p, q) to the spanning tree where q is the root of a subtree.
+ """
+ last_p = self.last_descendent_dft[p]
+ next_last_p = self.next_node_dft[last_p]
+ size_q = self.subtree_size[q]
+ last_q = self.last_descendent_dft[q]
+ # Make q a child of p.
+ self.parent[q] = p
+ self.parent_edge[q] = i
+ # Insert the subtree rooted at q into the depth-first thread.
+ self.next_node_dft[last_p] = q
+ self.prev_node_dft[q] = last_p
+ self.prev_node_dft[next_last_p] = last_q
+ self.next_node_dft[last_q] = next_last_p
+ # Update the subtree sizes and last descendants of the (new) ancestors
+ # of q.
+ while p is not None:
+ self.subtree_size[p] += size_q
+ if self.last_descendent_dft[p] == last_p:
+ self.last_descendent_dft[p] = last_q
+ p = self.parent[p]
+
+ def update_potentials(self, i, p, q):
+ """
+ Update the potentials of the nodes in the subtree rooted at a node
+ q connected to its parent p by an edge i.
+ """
+ if q == self.edge_targets[i]:
+ d = self.node_potentials[p] - self.edge_weights[i] - self.node_potentials[q]
+ else:
+ d = self.node_potentials[p] + self.edge_weights[i] - self.node_potentials[q]
+ for q in self.trace_subtree(q):
+ self.node_potentials[q] += d
+
+ def reduced_cost(self, i):
+ """Returns the reduced cost of an edge i."""
+ c = (
+ self.edge_weights[i]
+ - self.node_potentials[self.edge_sources[i]]
+ + self.node_potentials[self.edge_targets[i]]
+ )
+ return c if self.edge_flow[i] == 0 else -c
+
+ def find_entering_edges(self):
+ """Yield entering edges until none can be found."""
+ if self.edge_count == 0:
+ return
+
+ # Entering edges are found by combining Dantzig's rule and Bland's
+ # rule. The edges are cyclically grouped into blocks of size B. Within
+ # each block, Dantzig's rule is applied to find an entering edge. The
+ # blocks to search is determined following Bland's rule.
+ B = int(ceil(sqrt(self.edge_count))) # pivot block size
+ M = (self.edge_count + B - 1) // B # number of blocks needed to cover all edges
+ m = 0 # number of consecutive blocks without eligible
+ # entering edges
+ f = 0 # first edge in block
+ while m < M:
+ # Determine the next block of edges.
+ l = f + B
+ if l <= self.edge_count:
+ edges = range(f, l)
+ else:
+ l -= self.edge_count
+ edges = chain(range(f, self.edge_count), range(l))
+ f = l
+ # Find the first edge with the lowest reduced cost.
+ i = min(edges, key=self.reduced_cost)
+ c = self.reduced_cost(i)
+ if c >= 0:
+ # No entering edge found in the current block.
+ m += 1
+ else:
+ # Entering edge found.
+ if self.edge_flow[i] == 0:
+ p = self.edge_sources[i]
+ q = self.edge_targets[i]
+ else:
+ p = self.edge_targets[i]
+ q = self.edge_sources[i]
+ yield i, p, q
+ m = 0
+ # All edges have nonnegative reduced costs. The current flow is
+ # optimal.
+
+ def residual_capacity(self, i, p):
+ """Returns the residual capacity of an edge i in the direction away
+ from its endpoint p.
+ """
+ return (
+ self.edge_capacities[i] - self.edge_flow[i]
+ if self.edge_sources[i] == p
+ else self.edge_flow[i]
+ )
+
+ def find_leaving_edge(self, Wn, We):
+ """Returns the leaving edge in a cycle represented by Wn and We."""
+ j, s = min(
+ zip(reversed(We), reversed(Wn)),
+ key=lambda i_p: self.residual_capacity(*i_p),
+ )
+ t = self.edge_targets[j] if self.edge_sources[j] == s else self.edge_sources[j]
+ return j, s, t
+
+
+@not_implemented_for("undirected")
+@nx._dispatchable(
+ node_attrs="demand", edge_attrs={"capacity": float("inf"), "weight": 0}
+)
+def network_simplex(G, demand="demand", capacity="capacity", weight="weight"):
+ r"""Find a minimum cost flow satisfying all demands in digraph G.
+
+ This is a primal network simplex algorithm that uses the leaving
+ arc rule to prevent cycling.
+
+ G is a digraph with edge costs and capacities and in which nodes
+ have demand, i.e., they want to send or receive some amount of
+ flow. A negative demand means that the node wants to send flow, a
+ positive demand means that the node want to receive flow. A flow on
+ the digraph G satisfies all demand if the net flow into each node
+ is equal to the demand of that node.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+ DiGraph on which a minimum cost flow satisfying all demands is
+ to be found.
+
+ demand : string
+ Nodes of the graph G are expected to have an attribute demand
+ that indicates how much flow a node wants to send (negative
+ demand) or receive (positive demand). Note that the sum of the
+ demands should be 0 otherwise the problem in not feasible. If
+ this attribute is not present, a node is considered to have 0
+ demand. Default value: 'demand'.
+
+ 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'.
+
+ weight : string
+ Edges of the graph G are expected to have an attribute weight
+ that indicates the cost incurred by sending one unit of flow on
+ that edge. If not present, the weight is considered to be 0.
+ Default value: 'weight'.
+
+ Returns
+ -------
+ flowCost : integer, float
+ Cost of a minimum cost flow satisfying all demands.
+
+ flowDict : dictionary
+ Dictionary of dictionaries keyed by nodes such that
+ flowDict[u][v] is the flow edge (u, v).
+
+ Raises
+ ------
+ NetworkXError
+ This exception is raised if the input graph is not directed or
+ not connected.
+
+ NetworkXUnfeasible
+ This exception is raised in the following situations:
+
+ * The sum of the demands is not zero. Then, there is no
+ flow satisfying all demands.
+ * There is no flow satisfying all demand.
+
+ NetworkXUnbounded
+ This exception is raised if the digraph G has a cycle of
+ negative cost and infinite capacity. Then, the cost of a flow
+ satisfying all demands is unbounded below.
+
+ Notes
+ -----
+ This algorithm is not guaranteed to work if edge weights or demands
+ are floating point numbers (overflows and roundoff errors can
+ cause problems). As a workaround you can use integer numbers by
+ multiplying the relevant edge attributes by a convenient
+ constant factor (eg 100).
+
+ See also
+ --------
+ cost_of_flow, max_flow_min_cost, min_cost_flow, min_cost_flow_cost
+
+ Examples
+ --------
+ A simple example of a min cost flow problem.
+
+ >>> G = nx.DiGraph()
+ >>> G.add_node("a", demand=-5)
+ >>> G.add_node("d", demand=5)
+ >>> G.add_edge("a", "b", weight=3, capacity=4)
+ >>> G.add_edge("a", "c", weight=6, capacity=10)
+ >>> G.add_edge("b", "d", weight=1, capacity=9)
+ >>> G.add_edge("c", "d", weight=2, capacity=5)
+ >>> flowCost, flowDict = nx.network_simplex(G)
+ >>> flowCost
+ 24
+ >>> flowDict
+ {'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
+
+ The mincost flow algorithm can also be used to solve shortest path
+ problems. To find the shortest path between two nodes u and v,
+ give all edges an infinite capacity, give node u a demand of -1 and
+ node v a demand a 1. Then run the network simplex. The value of a
+ min cost flow will be the distance between u and v and edges
+ carrying positive flow will indicate the path.
+
+ >>> G = nx.DiGraph()
+ >>> G.add_weighted_edges_from(
+ ... [
+ ... ("s", "u", 10),
+ ... ("s", "x", 5),
+ ... ("u", "v", 1),
+ ... ("u", "x", 2),
+ ... ("v", "y", 1),
+ ... ("x", "u", 3),
+ ... ("x", "v", 5),
+ ... ("x", "y", 2),
+ ... ("y", "s", 7),
+ ... ("y", "v", 6),
+ ... ]
+ ... )
+ >>> G.add_node("s", demand=-1)
+ >>> G.add_node("v", demand=1)
+ >>> flowCost, flowDict = nx.network_simplex(G)
+ >>> flowCost == nx.shortest_path_length(G, "s", "v", weight="weight")
+ True
+ >>> sorted([(u, v) for u in flowDict for v in flowDict[u] if flowDict[u][v] > 0])
+ [('s', 'x'), ('u', 'v'), ('x', 'u')]
+ >>> nx.shortest_path(G, "s", "v", weight="weight")
+ ['s', 'x', 'u', 'v']
+
+ It is possible to change the name of the attributes used for the
+ algorithm.
+
+ >>> G = nx.DiGraph()
+ >>> G.add_node("p", spam=-4)
+ >>> G.add_node("q", spam=2)
+ >>> G.add_node("a", spam=-2)
+ >>> G.add_node("d", spam=-1)
+ >>> G.add_node("t", spam=2)
+ >>> G.add_node("w", spam=3)
+ >>> G.add_edge("p", "q", cost=7, vacancies=5)
+ >>> G.add_edge("p", "a", cost=1, vacancies=4)
+ >>> G.add_edge("q", "d", cost=2, vacancies=3)
+ >>> G.add_edge("t", "q", cost=1, vacancies=2)
+ >>> G.add_edge("a", "t", cost=2, vacancies=4)
+ >>> G.add_edge("d", "w", cost=3, vacancies=4)
+ >>> G.add_edge("t", "w", cost=4, vacancies=1)
+ >>> flowCost, flowDict = nx.network_simplex(
+ ... G, demand="spam", capacity="vacancies", weight="cost"
+ ... )
+ >>> flowCost
+ 37
+ >>> flowDict
+ {'p': {'q': 2, 'a': 2}, 'q': {'d': 1}, 'a': {'t': 4}, 'd': {'w': 2}, 't': {'q': 1, 'w': 1}, 'w': {}}
+
+ References
+ ----------
+ .. [1] Z. Kiraly, P. Kovacs.
+ Efficient implementation of minimum-cost flow algorithms.
+ Acta Universitatis Sapientiae, Informatica 4(1):67--118. 2012.
+ .. [2] R. Barr, F. Glover, D. Klingman.
+ Enhancement of spanning tree labeling procedures for network
+ optimization.
+ INFOR 17(1):16--34. 1979.
+ """
+ ###########################################################################
+ # Problem essentials extraction and sanity check
+ ###########################################################################
+
+ if len(G) == 0:
+ raise nx.NetworkXError("graph has no nodes")
+
+ multigraph = G.is_multigraph()
+
+ # extracting data essential to problem
+ DEAF = _DataEssentialsAndFunctions(
+ G, multigraph, demand=demand, capacity=capacity, weight=weight
+ )
+
+ ###########################################################################
+ # Quick Error Detection
+ ###########################################################################
+
+ inf = float("inf")
+ for u, d in zip(DEAF.node_list, DEAF.node_demands):
+ if abs(d) == inf:
+ raise nx.NetworkXError(f"node {u!r} has infinite demand")
+ for e, w in zip(DEAF.edge_indices, DEAF.edge_weights):
+ if abs(w) == inf:
+ raise nx.NetworkXError(f"edge {e!r} has infinite weight")
+ if not multigraph:
+ edges = nx.selfloop_edges(G, data=True)
+ else:
+ edges = nx.selfloop_edges(G, data=True, keys=True)
+ for e in edges:
+ if abs(e[-1].get(weight, 0)) == inf:
+ raise nx.NetworkXError(f"edge {e[:-1]!r} has infinite weight")
+
+ ###########################################################################
+ # Quick Infeasibility Detection
+ ###########################################################################
+
+ if sum(DEAF.node_demands) != 0:
+ raise nx.NetworkXUnfeasible("total node demand is not zero")
+ for e, c in zip(DEAF.edge_indices, DEAF.edge_capacities):
+ if c < 0:
+ raise nx.NetworkXUnfeasible(f"edge {e!r} has negative capacity")
+ if not multigraph:
+ edges = nx.selfloop_edges(G, data=True)
+ else:
+ edges = nx.selfloop_edges(G, data=True, keys=True)
+ for e in edges:
+ if e[-1].get(capacity, inf) < 0:
+ raise nx.NetworkXUnfeasible(f"edge {e[:-1]!r} has negative capacity")
+
+ ###########################################################################
+ # Initialization
+ ###########################################################################
+
+ # Add a dummy node -1 and connect all existing nodes to it with infinite-
+ # capacity dummy edges. Node -1 will serve as the root of the
+ # spanning tree of the network simplex method. The new edges will used to
+ # trivially satisfy the node demands and create an initial strongly
+ # feasible spanning tree.
+ for i, d in enumerate(DEAF.node_demands):
+ # Must be greater-than here. Zero-demand nodes must have
+ # edges pointing towards the root to ensure strong feasibility.
+ if d > 0:
+ DEAF.edge_sources.append(-1)
+ DEAF.edge_targets.append(i)
+ else:
+ DEAF.edge_sources.append(i)
+ DEAF.edge_targets.append(-1)
+ faux_inf = (
+ 3
+ * max(
+ chain(
+ [
+ sum(c for c in DEAF.edge_capacities if c < inf),
+ sum(abs(w) for w in DEAF.edge_weights),
+ ],
+ (abs(d) for d in DEAF.node_demands),
+ )
+ )
+ or 1
+ )
+
+ n = len(DEAF.node_list) # number of nodes
+ DEAF.edge_weights.extend(repeat(faux_inf, n))
+ DEAF.edge_capacities.extend(repeat(faux_inf, n))
+
+ # Construct the initial spanning tree.
+ DEAF.initialize_spanning_tree(n, faux_inf)
+
+ ###########################################################################
+ # Pivot loop
+ ###########################################################################
+
+ for i, p, q in DEAF.find_entering_edges():
+ Wn, We = DEAF.find_cycle(i, p, q)
+ j, s, t = DEAF.find_leaving_edge(Wn, We)
+ DEAF.augment_flow(Wn, We, DEAF.residual_capacity(j, s))
+ # Do nothing more if the entering edge is the same as the leaving edge.
+ if i != j:
+ if DEAF.parent[t] != s:
+ # Ensure that s is the parent of t.
+ s, t = t, s
+ if We.index(i) > We.index(j):
+ # Ensure that q is in the subtree rooted at t.
+ p, q = q, p
+ DEAF.remove_edge(s, t)
+ DEAF.make_root(q)
+ DEAF.add_edge(i, p, q)
+ DEAF.update_potentials(i, p, q)
+
+ ###########################################################################
+ # Infeasibility and unboundedness detection
+ ###########################################################################
+
+ if any(DEAF.edge_flow[i] != 0 for i in range(-n, 0)):
+ raise nx.NetworkXUnfeasible("no flow satisfies all node demands")
+
+ if any(DEAF.edge_flow[i] * 2 >= faux_inf for i in range(DEAF.edge_count)) or any(
+ e[-1].get(capacity, inf) == inf and e[-1].get(weight, 0) < 0
+ for e in nx.selfloop_edges(G, data=True)
+ ):
+ raise nx.NetworkXUnbounded("negative cycle with infinite capacity found")
+
+ ###########################################################################
+ # Flow cost calculation and flow dict construction
+ ###########################################################################
+
+ del DEAF.edge_flow[DEAF.edge_count :]
+ flow_cost = sum(w * x for w, x in zip(DEAF.edge_weights, DEAF.edge_flow))
+ flow_dict = {n: {} for n in DEAF.node_list}
+
+ def add_entry(e):
+ """Add a flow dict entry."""
+ d = flow_dict[e[0]]
+ for k in e[1:-2]:
+ try:
+ d = d[k]
+ except KeyError:
+ t = {}
+ d[k] = t
+ d = t
+ d[e[-2]] = e[-1]
+
+ DEAF.edge_sources = (
+ DEAF.node_list[s] for s in DEAF.edge_sources
+ ) # Use original nodes.
+ DEAF.edge_targets = (
+ DEAF.node_list[t] for t in DEAF.edge_targets
+ ) # Use original nodes.
+ if not multigraph:
+ for e in zip(DEAF.edge_sources, DEAF.edge_targets, DEAF.edge_flow):
+ add_entry(e)
+ edges = G.edges(data=True)
+ else:
+ for e in zip(
+ DEAF.edge_sources, DEAF.edge_targets, DEAF.edge_keys, DEAF.edge_flow
+ ):
+ add_entry(e)
+ edges = G.edges(data=True, keys=True)
+ for e in edges:
+ if e[0] != e[1]:
+ if e[-1].get(capacity, inf) == 0:
+ add_entry(e[:-1] + (0,))
+ else:
+ w = e[-1].get(weight, 0)
+ if w >= 0:
+ add_entry(e[:-1] + (0,))
+ else:
+ c = e[-1][capacity]
+ flow_cost += w * c
+ add_entry(e[:-1] + (c,))
+
+ return flow_cost, flow_dict
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/preflowpush.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/preflowpush.py
new file mode 100644
index 00000000..42cadc2e
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/preflowpush.py
@@ -0,0 +1,425 @@
+"""
+Highest-label preflow-push algorithm for maximum flow problems.
+"""
+
+from collections import deque
+from itertools import islice
+
+import networkx as nx
+
+from ...utils import arbitrary_element
+from .utils import (
+ CurrentEdge,
+ GlobalRelabelThreshold,
+ Level,
+ build_residual_network,
+ detect_unboundedness,
+)
+
+__all__ = ["preflow_push"]
+
+
+def preflow_push_impl(G, s, t, capacity, residual, global_relabel_freq, value_only):
+ """Implementation of the highest-label preflow-push 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 global_relabel_freq is None:
+ global_relabel_freq = 0
+ if global_relabel_freq < 0:
+ raise nx.NetworkXError("global_relabel_freq must be nonnegative.")
+
+ if residual is None:
+ R = build_residual_network(G, capacity)
+ else:
+ R = residual
+
+ detect_unboundedness(R, s, t)
+
+ R_nodes = R.nodes
+ R_pred = R.pred
+ R_succ = R.succ
+
+ # Initialize/reset the residual network.
+ for u in R:
+ R_nodes[u]["excess"] = 0
+ for e in R_succ[u].values():
+ e["flow"] = 0
+
+ def reverse_bfs(src):
+ """Perform a reverse breadth-first search from src in the residual
+ network.
+ """
+ heights = {src: 0}
+ q = deque([(src, 0)])
+ while q:
+ u, height = q.popleft()
+ height += 1
+ for v, attr in R_pred[u].items():
+ if v not in heights and attr["flow"] < attr["capacity"]:
+ heights[v] = height
+ q.append((v, height))
+ return heights
+
+ # Initialize heights of the nodes.
+ heights = reverse_bfs(t)
+
+ if s not in heights:
+ # t is not reachable from s in the residual network. The maximum flow
+ # must be zero.
+ R.graph["flow_value"] = 0
+ return R
+
+ n = len(R)
+ # max_height represents the height of the highest level below level n with
+ # at least one active node.
+ max_height = max(heights[u] for u in heights if u != s)
+ heights[s] = n
+
+ grt = GlobalRelabelThreshold(n, R.size(), global_relabel_freq)
+
+ # Initialize heights and 'current edge' data structures of the nodes.
+ for u in R:
+ R_nodes[u]["height"] = heights[u] if u in heights else n + 1
+ R_nodes[u]["curr_edge"] = CurrentEdge(R_succ[u])
+
+ def push(u, v, flow):
+ """Push flow units of flow from u to v."""
+ R_succ[u][v]["flow"] += flow
+ R_succ[v][u]["flow"] -= flow
+ R_nodes[u]["excess"] -= flow
+ R_nodes[v]["excess"] += flow
+
+ # The maximum flow must be nonzero now. Initialize the preflow by
+ # saturating all edges emanating from s.
+ for u, attr in R_succ[s].items():
+ flow = attr["capacity"]
+ if flow > 0:
+ push(s, u, flow)
+
+ # Partition nodes into levels.
+ levels = [Level() for i in range(2 * n)]
+ for u in R:
+ if u != s and u != t:
+ level = levels[R_nodes[u]["height"]]
+ if R_nodes[u]["excess"] > 0:
+ level.active.add(u)
+ else:
+ level.inactive.add(u)
+
+ def activate(v):
+ """Move a node from the inactive set to the active set of its level."""
+ if v != s and v != t:
+ level = levels[R_nodes[v]["height"]]
+ if v in level.inactive:
+ level.inactive.remove(v)
+ level.active.add(v)
+
+ def relabel(u):
+ """Relabel a node to create an admissible edge."""
+ grt.add_work(len(R_succ[u]))
+ return (
+ min(
+ R_nodes[v]["height"]
+ for v, attr in R_succ[u].items()
+ if attr["flow"] < attr["capacity"]
+ )
+ + 1
+ )
+
+ def discharge(u, is_phase1):
+ """Discharge a node until it becomes inactive or, during phase 1 (see
+ below), its height reaches at least n. The node is known to have the
+ largest height among active nodes.
+ """
+ height = R_nodes[u]["height"]
+ curr_edge = R_nodes[u]["curr_edge"]
+ # next_height represents the next height to examine after discharging
+ # the current node. During phase 1, it is capped to below n.
+ next_height = height
+ levels[height].active.remove(u)
+ while True:
+ v, attr = curr_edge.get()
+ if height == R_nodes[v]["height"] + 1 and attr["flow"] < attr["capacity"]:
+ flow = min(R_nodes[u]["excess"], attr["capacity"] - attr["flow"])
+ push(u, v, flow)
+ activate(v)
+ if R_nodes[u]["excess"] == 0:
+ # The node has become inactive.
+ levels[height].inactive.add(u)
+ break
+ try:
+ curr_edge.move_to_next()
+ except StopIteration:
+ # We have run off the end of the adjacency list, and there can
+ # be no more admissible edges. Relabel the node to create one.
+ height = relabel(u)
+ if is_phase1 and height >= n - 1:
+ # Although the node is still active, with a height at least
+ # n - 1, it is now known to be on the s side of the minimum
+ # s-t cut. Stop processing it until phase 2.
+ levels[height].active.add(u)
+ break
+ # The first relabel operation after global relabeling may not
+ # increase the height of the node since the 'current edge' data
+ # structure is not rewound. Use height instead of (height - 1)
+ # in case other active nodes at the same level are missed.
+ next_height = height
+ R_nodes[u]["height"] = height
+ return next_height
+
+ def gap_heuristic(height):
+ """Apply the gap heuristic."""
+ # Move all nodes at levels (height + 1) to max_height to level n + 1.
+ for level in islice(levels, height + 1, max_height + 1):
+ for u in level.active:
+ R_nodes[u]["height"] = n + 1
+ for u in level.inactive:
+ R_nodes[u]["height"] = n + 1
+ levels[n + 1].active.update(level.active)
+ level.active.clear()
+ levels[n + 1].inactive.update(level.inactive)
+ level.inactive.clear()
+
+ def global_relabel(from_sink):
+ """Apply the global relabeling heuristic."""
+ src = t if from_sink else s
+ heights = reverse_bfs(src)
+ if not from_sink:
+ # s must be reachable from t. Remove t explicitly.
+ del heights[t]
+ max_height = max(heights.values())
+ if from_sink:
+ # Also mark nodes from which t is unreachable for relabeling. This
+ # serves the same purpose as the gap heuristic.
+ for u in R:
+ if u not in heights and R_nodes[u]["height"] < n:
+ heights[u] = n + 1
+ else:
+ # Shift the computed heights because the height of s is n.
+ for u in heights:
+ heights[u] += n
+ max_height += n
+ del heights[src]
+ for u, new_height in heights.items():
+ old_height = R_nodes[u]["height"]
+ if new_height != old_height:
+ if u in levels[old_height].active:
+ levels[old_height].active.remove(u)
+ levels[new_height].active.add(u)
+ else:
+ levels[old_height].inactive.remove(u)
+ levels[new_height].inactive.add(u)
+ R_nodes[u]["height"] = new_height
+ return max_height
+
+ # Phase 1: Find the maximum preflow by pushing as much flow as possible to
+ # t.
+
+ height = max_height
+ while height > 0:
+ # Discharge active nodes in the current level.
+ while True:
+ level = levels[height]
+ if not level.active:
+ # All active nodes in the current level have been discharged.
+ # Move to the next lower level.
+ height -= 1
+ break
+ # Record the old height and level for the gap heuristic.
+ old_height = height
+ old_level = level
+ u = arbitrary_element(level.active)
+ height = discharge(u, True)
+ if grt.is_reached():
+ # Global relabeling heuristic: Recompute the exact heights of
+ # all nodes.
+ height = global_relabel(True)
+ max_height = height
+ grt.clear_work()
+ elif not old_level.active and not old_level.inactive:
+ # Gap heuristic: If the level at old_height is empty (a 'gap'),
+ # a minimum cut has been identified. All nodes with heights
+ # above old_height can have their heights set to n + 1 and not
+ # be further processed before a maximum preflow is found.
+ gap_heuristic(old_height)
+ height = old_height - 1
+ max_height = height
+ else:
+ # Update the height of the highest level with at least one
+ # active node.
+ max_height = max(max_height, height)
+
+ # A maximum preflow has been found. The excess at t is the maximum flow
+ # value.
+ if value_only:
+ R.graph["flow_value"] = R_nodes[t]["excess"]
+ return R
+
+ # Phase 2: Convert the maximum preflow into a maximum flow by returning the
+ # excess to s.
+
+ # Relabel all nodes so that they have accurate heights.
+ height = global_relabel(False)
+ grt.clear_work()
+
+ # Continue to discharge the active nodes.
+ while height > n:
+ # Discharge active nodes in the current level.
+ while True:
+ level = levels[height]
+ if not level.active:
+ # All active nodes in the current level have been discharged.
+ # Move to the next lower level.
+ height -= 1
+ break
+ u = arbitrary_element(level.active)
+ height = discharge(u, False)
+ if grt.is_reached():
+ # Global relabeling heuristic.
+ height = global_relabel(False)
+ grt.clear_work()
+
+ R.graph["flow_value"] = R_nodes[t]["excess"]
+ return R
+
+
+@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
+def preflow_push(
+ G, s, t, capacity="capacity", residual=None, global_relabel_freq=1, value_only=False
+):
+ r"""Find a maximum single-commodity flow using the highest-label
+ preflow-push 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^2 \sqrt{m})$ 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.
+
+ global_relabel_freq : integer, float
+ Relative frequency of applying the global relabeling heuristic to speed
+ up the algorithm. If it is None, the heuristic is disabled. Default
+ value: 1.
+
+ value_only : bool
+ If False, compute a maximum flow; otherwise, compute a maximum preflow
+ which is enough for computing the maximum flow value. Default value:
+ False.
+
+ 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:`edmonds_karp`
+ :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 node :samp:`u` in :samp:`R`,
+ :samp:`R.nodes[u]['excess']` represents the difference between flow into
+ :samp:`u` and flow out of :samp:`u`.
+
+ 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']`. 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 preflow_push
+
+ 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 = preflow_push(G, "x", "y")
+ >>> flow_value = nx.maximum_flow_value(G, "x", "y")
+ >>> flow_value == R.graph["flow_value"]
+ True
+ >>> # preflow_push also stores the maximum flow value
+ >>> # in the excess attribute of the sink node t
+ >>> flow_value == R.nodes["y"]["excess"]
+ True
+ >>> # For some problems, you might only want to compute a
+ >>> # maximum preflow.
+ >>> R = preflow_push(G, "x", "y", value_only=True)
+ >>> flow_value == R.graph["flow_value"]
+ True
+ >>> flow_value == R.nodes["y"]["excess"]
+ True
+
+ """
+ R = preflow_push_impl(G, s, t, capacity, residual, global_relabel_freq, value_only)
+ R.graph["algorithm"] = "preflow_push"
+ nx._clear_cache(R)
+ return R
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/shortestaugmentingpath.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/shortestaugmentingpath.py
new file mode 100644
index 00000000..9f1193f1
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/shortestaugmentingpath.py
@@ -0,0 +1,300 @@
+"""
+Shortest augmenting path algorithm for maximum flow problems.
+"""
+
+from collections import deque
+
+import networkx as nx
+
+from .edmondskarp import edmonds_karp_core
+from .utils import CurrentEdge, build_residual_network
+
+__all__ = ["shortest_augmenting_path"]
+
+
+def shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff):
+ """Implementation of the shortest augmenting path 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
+
+ R_nodes = R.nodes
+ R_pred = R.pred
+ R_succ = R.succ
+
+ # Initialize/reset the residual network.
+ for u in R:
+ for e in R_succ[u].values():
+ e["flow"] = 0
+
+ # Initialize heights of the nodes.
+ heights = {t: 0}
+ q = deque([(t, 0)])
+ while q:
+ u, height = q.popleft()
+ height += 1
+ for v, attr in R_pred[u].items():
+ if v not in heights and attr["flow"] < attr["capacity"]:
+ heights[v] = height
+ q.append((v, height))
+
+ if s not in heights:
+ # t is not reachable from s in the residual network. The maximum flow
+ # must be zero.
+ R.graph["flow_value"] = 0
+ return R
+
+ n = len(G)
+ m = R.size() / 2
+
+ # Initialize heights and 'current edge' data structures of the nodes.
+ for u in R:
+ R_nodes[u]["height"] = heights[u] if u in heights else n
+ R_nodes[u]["curr_edge"] = CurrentEdge(R_succ[u])
+
+ # Initialize counts of nodes in each level.
+ counts = [0] * (2 * n - 1)
+ for u in R:
+ counts[R_nodes[u]["height"]] += 1
+
+ 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 relabel(u):
+ """Relabel a node to create an admissible edge."""
+ height = n - 1
+ for v, attr in R_succ[u].items():
+ if attr["flow"] < attr["capacity"]:
+ height = min(height, R_nodes[v]["height"])
+ return height + 1
+
+ if cutoff is None:
+ cutoff = float("inf")
+
+ # Phase 1: Look for shortest augmenting paths using depth-first search.
+
+ flow_value = 0
+ path = [s]
+ u = s
+ d = n if not two_phase else int(min(m**0.5, 2 * n ** (2.0 / 3)))
+ done = R_nodes[s]["height"] >= d
+ while not done:
+ height = R_nodes[u]["height"]
+ curr_edge = R_nodes[u]["curr_edge"]
+ # Depth-first search for the next node on the path to t.
+ while True:
+ v, attr = curr_edge.get()
+ if height == R_nodes[v]["height"] + 1 and attr["flow"] < attr["capacity"]:
+ # Advance to the next node following an admissible edge.
+ path.append(v)
+ u = v
+ break
+ try:
+ curr_edge.move_to_next()
+ except StopIteration:
+ counts[height] -= 1
+ if counts[height] == 0:
+ # Gap heuristic: If relabeling causes a level to become
+ # empty, a minimum cut has been identified. The algorithm
+ # can now be terminated.
+ R.graph["flow_value"] = flow_value
+ return R
+ height = relabel(u)
+ if u == s and height >= d:
+ if not two_phase:
+ # t is disconnected from s in the residual network. No
+ # more augmenting paths exist.
+ R.graph["flow_value"] = flow_value
+ return R
+ else:
+ # t is at least d steps away from s. End of phase 1.
+ done = True
+ break
+ counts[height] += 1
+ R_nodes[u]["height"] = height
+ if u != s:
+ # After relabeling, the last edge on the path is no longer
+ # admissible. Retreat one step to look for an alternative.
+ path.pop()
+ u = path[-1]
+ break
+ if u == t:
+ # t is reached. Augment flow along the path and reset it for a new
+ # depth-first search.
+ flow_value += augment(path)
+ if flow_value >= cutoff:
+ R.graph["flow_value"] = flow_value
+ return R
+ path = [s]
+ u = s
+
+ # Phase 2: Look for shortest augmenting paths using breadth-first search.
+ flow_value += edmonds_karp_core(R, s, t, cutoff - flow_value)
+
+ R.graph["flow_value"] = flow_value
+ return R
+
+
+@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
+def shortest_augmenting_path(
+ G,
+ s,
+ t,
+ capacity="capacity",
+ residual=None,
+ value_only=False,
+ two_phase=False,
+ cutoff=None,
+):
+ r"""Find a maximum single-commodity flow using the shortest augmenting path
+ 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^2 m)$ 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.
+
+ two_phase : bool
+ If True, a two-phase variant is used. The two-phase variant improves
+ the running time on unit-capacity networks from $O(nm)$ to
+ $O(\min(n^{2/3}, m^{1/2}) m)$. Default value: False.
+
+ 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:`edmonds_karp`
+ :meth:`preflow_push`
+
+ 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 shortest_augmenting_path
+
+ 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 = shortest_augmenting_path(G, "x", "y")
+ >>> flow_value = nx.maximum_flow_value(G, "x", "y")
+ >>> flow_value
+ 3.0
+ >>> flow_value == R.graph["flow_value"]
+ True
+
+ """
+ R = shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase, cutoff)
+ R.graph["algorithm"] = "shortest_augmenting_path"
+ nx._clear_cache(R)
+ return R
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/__init__.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/__init__.py
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/__init__.py
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gl1.gpickle.bz2 b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gl1.gpickle.bz2
new file mode 100644
index 00000000..e6ed5744
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gl1.gpickle.bz2
Binary files differ
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gw1.gpickle.bz2 b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gw1.gpickle.bz2
new file mode 100644
index 00000000..abd0e8a2
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/gw1.gpickle.bz2
Binary files differ
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/netgen-2.gpickle.bz2 b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/netgen-2.gpickle.bz2
new file mode 100644
index 00000000..cd3ea801
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/netgen-2.gpickle.bz2
Binary files differ
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_gomory_hu.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_gomory_hu.py
new file mode 100644
index 00000000..1649ec82
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_gomory_hu.py
@@ -0,0 +1,128 @@
+from itertools import combinations
+
+import pytest
+
+import networkx as nx
+from networkx.algorithms.flow import (
+ boykov_kolmogorov,
+ dinitz,
+ edmonds_karp,
+ preflow_push,
+ shortest_augmenting_path,
+)
+
+flow_funcs = [
+ boykov_kolmogorov,
+ dinitz,
+ edmonds_karp,
+ preflow_push,
+ shortest_augmenting_path,
+]
+
+
+class TestGomoryHuTree:
+ def minimum_edge_weight(self, T, u, v):
+ path = nx.shortest_path(T, u, v, weight="weight")
+ return min((T[u][v]["weight"], (u, v)) for (u, v) in zip(path, path[1:]))
+
+ def compute_cutset(self, G, T_orig, edge):
+ T = T_orig.copy()
+ T.remove_edge(*edge)
+ U, V = list(nx.connected_components(T))
+ cutset = set()
+ for x, nbrs in ((n, G[n]) for n in U):
+ cutset.update((x, y) for y in nbrs if y in V)
+ return cutset
+
+ def test_default_flow_function_karate_club_graph(self):
+ G = nx.karate_club_graph()
+ nx.set_edge_attributes(G, 1, "capacity")
+ T = nx.gomory_hu_tree(G)
+ assert nx.is_tree(T)
+ for u, v in combinations(G, 2):
+ cut_value, edge = self.minimum_edge_weight(T, u, v)
+ assert nx.minimum_cut_value(G, u, v) == cut_value
+
+ def test_karate_club_graph(self):
+ G = nx.karate_club_graph()
+ nx.set_edge_attributes(G, 1, "capacity")
+ for flow_func in flow_funcs:
+ T = nx.gomory_hu_tree(G, flow_func=flow_func)
+ assert nx.is_tree(T)
+ for u, v in combinations(G, 2):
+ cut_value, edge = self.minimum_edge_weight(T, u, v)
+ assert nx.minimum_cut_value(G, u, v) == cut_value
+
+ def test_davis_southern_women_graph(self):
+ G = nx.davis_southern_women_graph()
+ nx.set_edge_attributes(G, 1, "capacity")
+ for flow_func in flow_funcs:
+ T = nx.gomory_hu_tree(G, flow_func=flow_func)
+ assert nx.is_tree(T)
+ for u, v in combinations(G, 2):
+ cut_value, edge = self.minimum_edge_weight(T, u, v)
+ assert nx.minimum_cut_value(G, u, v) == cut_value
+
+ def test_florentine_families_graph(self):
+ G = nx.florentine_families_graph()
+ nx.set_edge_attributes(G, 1, "capacity")
+ for flow_func in flow_funcs:
+ T = nx.gomory_hu_tree(G, flow_func=flow_func)
+ assert nx.is_tree(T)
+ for u, v in combinations(G, 2):
+ cut_value, edge = self.minimum_edge_weight(T, u, v)
+ assert nx.minimum_cut_value(G, u, v) == cut_value
+
+ @pytest.mark.slow
+ def test_les_miserables_graph_cutset(self):
+ G = nx.les_miserables_graph()
+ nx.set_edge_attributes(G, 1, "capacity")
+ for flow_func in flow_funcs:
+ T = nx.gomory_hu_tree(G, flow_func=flow_func)
+ assert nx.is_tree(T)
+ for u, v in combinations(G, 2):
+ cut_value, edge = self.minimum_edge_weight(T, u, v)
+ assert nx.minimum_cut_value(G, u, v) == cut_value
+
+ def test_karate_club_graph_cutset(self):
+ G = nx.karate_club_graph()
+ nx.set_edge_attributes(G, 1, "capacity")
+ T = nx.gomory_hu_tree(G)
+ assert nx.is_tree(T)
+ u, v = 0, 33
+ cut_value, edge = self.minimum_edge_weight(T, u, v)
+ cutset = self.compute_cutset(G, T, edge)
+ assert cut_value == len(cutset)
+
+ def test_wikipedia_example(self):
+ # Example from https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree
+ G = nx.Graph()
+ G.add_weighted_edges_from(
+ (
+ (0, 1, 1),
+ (0, 2, 7),
+ (1, 2, 1),
+ (1, 3, 3),
+ (1, 4, 2),
+ (2, 4, 4),
+ (3, 4, 1),
+ (3, 5, 6),
+ (4, 5, 2),
+ )
+ )
+ for flow_func in flow_funcs:
+ T = nx.gomory_hu_tree(G, capacity="weight", flow_func=flow_func)
+ assert nx.is_tree(T)
+ for u, v in combinations(G, 2):
+ cut_value, edge = self.minimum_edge_weight(T, u, v)
+ assert nx.minimum_cut_value(G, u, v, capacity="weight") == cut_value
+
+ def test_directed_raises(self):
+ with pytest.raises(nx.NetworkXNotImplemented):
+ G = nx.DiGraph()
+ T = nx.gomory_hu_tree(G)
+
+ def test_empty_raises(self):
+ with pytest.raises(nx.NetworkXError):
+ G = nx.empty_graph()
+ T = nx.gomory_hu_tree(G)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow.py
new file mode 100644
index 00000000..d7305a7b
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow.py
@@ -0,0 +1,573 @@
+"""Maximum flow algorithms test suite."""
+
+import pytest
+
+import networkx as nx
+from networkx.algorithms.flow import (
+ boykov_kolmogorov,
+ build_flow_dict,
+ build_residual_network,
+ dinitz,
+ edmonds_karp,
+ preflow_push,
+ shortest_augmenting_path,
+)
+
+flow_funcs = {
+ boykov_kolmogorov,
+ dinitz,
+ edmonds_karp,
+ preflow_push,
+ shortest_augmenting_path,
+}
+
+max_min_funcs = {nx.maximum_flow, nx.minimum_cut}
+flow_value_funcs = {nx.maximum_flow_value, nx.minimum_cut_value}
+interface_funcs = max_min_funcs | flow_value_funcs
+all_funcs = flow_funcs | interface_funcs
+
+
+def compute_cutset(G, partition):
+ reachable, non_reachable = partition
+ cutset = set()
+ for u, nbrs in ((n, G[n]) for n in reachable):
+ cutset.update((u, v) for v in nbrs if v in non_reachable)
+ return cutset
+
+
+def validate_flows(G, s, t, flowDict, solnValue, capacity, flow_func):
+ errmsg = f"Assertion failed in function: {flow_func.__name__}"
+ assert set(G) == set(flowDict), errmsg
+ for u in G:
+ assert set(G[u]) == set(flowDict[u]), errmsg
+ excess = {u: 0 for u in flowDict}
+ for u in flowDict:
+ for v, flow in flowDict[u].items():
+ if capacity in G[u][v]:
+ assert flow <= G[u][v][capacity]
+ assert flow >= 0, errmsg
+ excess[u] -= flow
+ excess[v] += flow
+ for u, exc in excess.items():
+ if u == s:
+ assert exc == -solnValue, errmsg
+ elif u == t:
+ assert exc == solnValue, errmsg
+ else:
+ assert exc == 0, errmsg
+
+
+def validate_cuts(G, s, t, solnValue, partition, capacity, flow_func):
+ errmsg = f"Assertion failed in function: {flow_func.__name__}"
+ assert all(n in G for n in partition[0]), errmsg
+ assert all(n in G for n in partition[1]), errmsg
+ cutset = compute_cutset(G, partition)
+ assert all(G.has_edge(u, v) for (u, v) in cutset), errmsg
+ assert solnValue == sum(G[u][v][capacity] for (u, v) in cutset), errmsg
+ H = G.copy()
+ H.remove_edges_from(cutset)
+ if not G.is_directed():
+ assert not nx.is_connected(H), errmsg
+ else:
+ assert not nx.is_strongly_connected(H), errmsg
+
+
+def compare_flows_and_cuts(G, s, t, solnValue, capacity="capacity"):
+ for flow_func in flow_funcs:
+ errmsg = f"Assertion failed in function: {flow_func.__name__}"
+ R = flow_func(G, s, t, capacity)
+ # Test both legacy and new implementations.
+ flow_value = R.graph["flow_value"]
+ flow_dict = build_flow_dict(G, R)
+ assert flow_value == solnValue, errmsg
+ validate_flows(G, s, t, flow_dict, solnValue, capacity, flow_func)
+ # Minimum cut
+ cut_value, partition = nx.minimum_cut(
+ G, s, t, capacity=capacity, flow_func=flow_func
+ )
+ validate_cuts(G, s, t, solnValue, partition, capacity, flow_func)
+
+
+class TestMaxflowMinCutCommon:
+ def test_graph1(self):
+ # Trivial undirected graph
+ G = nx.Graph()
+ G.add_edge(1, 2, capacity=1.0)
+
+ # solution flows
+ # {1: {2: 1.0}, 2: {1: 1.0}}
+
+ compare_flows_and_cuts(G, 1, 2, 1.0)
+
+ def test_graph2(self):
+ # A more complex undirected graph
+ # adapted from https://web.archive.org/web/20220815055650/https://www.topcoder.com/thrive/articles/Maximum%20Flow:%20Part%20One
+ G = nx.Graph()
+ 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)
+
+ # H
+ # {
+ # "x": {"a": 3, "b": 1},
+ # "a": {"c": 3, "x": 3},
+ # "b": {"c": 1, "d": 2, "x": 1},
+ # "c": {"a": 3, "b": 1, "y": 2},
+ # "d": {"b": 2, "e": 2},
+ # "e": {"d": 2, "y": 2},
+ # "y": {"c": 2, "e": 2},
+ # }
+
+ compare_flows_and_cuts(G, "x", "y", 4.0)
+
+ def test_digraph1(self):
+ # The classic directed graph example
+ G = nx.DiGraph()
+ G.add_edge("a", "b", capacity=1000.0)
+ G.add_edge("a", "c", capacity=1000.0)
+ G.add_edge("b", "c", capacity=1.0)
+ G.add_edge("b", "d", capacity=1000.0)
+ G.add_edge("c", "d", capacity=1000.0)
+
+ # H
+ # {
+ # "a": {"b": 1000.0, "c": 1000.0},
+ # "b": {"c": 0, "d": 1000.0},
+ # "c": {"d": 1000.0},
+ # "d": {},
+ # }
+
+ compare_flows_and_cuts(G, "a", "d", 2000.0)
+
+ def test_digraph2(self):
+ # An example in which some edges end up with zero flow.
+ G = nx.DiGraph()
+ G.add_edge("s", "b", capacity=2)
+ G.add_edge("s", "c", capacity=1)
+ G.add_edge("c", "d", capacity=1)
+ G.add_edge("d", "a", capacity=1)
+ G.add_edge("b", "a", capacity=2)
+ G.add_edge("a", "t", capacity=2)
+
+ # H
+ # {
+ # "s": {"b": 2, "c": 0},
+ # "c": {"d": 0},
+ # "d": {"a": 0},
+ # "b": {"a": 2},
+ # "a": {"t": 2},
+ # "t": {},
+ # }
+
+ compare_flows_and_cuts(G, "s", "t", 2)
+
+ def test_digraph3(self):
+ # A directed graph example from Cormen et al.
+ G = nx.DiGraph()
+ G.add_edge("s", "v1", capacity=16.0)
+ G.add_edge("s", "v2", capacity=13.0)
+ G.add_edge("v1", "v2", capacity=10.0)
+ G.add_edge("v2", "v1", capacity=4.0)
+ G.add_edge("v1", "v3", capacity=12.0)
+ G.add_edge("v3", "v2", capacity=9.0)
+ G.add_edge("v2", "v4", capacity=14.0)
+ G.add_edge("v4", "v3", capacity=7.0)
+ G.add_edge("v3", "t", capacity=20.0)
+ G.add_edge("v4", "t", capacity=4.0)
+
+ # H
+ # {
+ # "s": {"v1": 12.0, "v2": 11.0},
+ # "v2": {"v1": 0, "v4": 11.0},
+ # "v1": {"v2": 0, "v3": 12.0},
+ # "v3": {"v2": 0, "t": 19.0},
+ # "v4": {"v3": 7.0, "t": 4.0},
+ # "t": {},
+ # }
+
+ compare_flows_and_cuts(G, "s", "t", 23.0)
+
+ def test_digraph4(self):
+ # A more complex directed graph
+ # from https://web.archive.org/web/20220815055650/https://www.topcoder.com/thrive/articles/Maximum%20Flow:%20Part%20One
+ 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)
+
+ # H
+ # {
+ # "x": {"a": 2.0, "b": 1.0},
+ # "a": {"c": 2.0},
+ # "b": {"c": 0, "d": 1.0},
+ # "c": {"y": 2.0},
+ # "d": {"e": 1.0},
+ # "e": {"y": 1.0},
+ # "y": {},
+ # }
+
+ compare_flows_and_cuts(G, "x", "y", 3.0)
+
+ def test_wikipedia_dinitz_example(self):
+ # Nice example from https://en.wikipedia.org/wiki/Dinic's_algorithm
+ G = nx.DiGraph()
+ G.add_edge("s", 1, capacity=10)
+ G.add_edge("s", 2, capacity=10)
+ G.add_edge(1, 3, capacity=4)
+ G.add_edge(1, 4, capacity=8)
+ G.add_edge(1, 2, capacity=2)
+ G.add_edge(2, 4, capacity=9)
+ G.add_edge(3, "t", capacity=10)
+ G.add_edge(4, 3, capacity=6)
+ G.add_edge(4, "t", capacity=10)
+
+ # solution flows
+ # {
+ # 1: {2: 0, 3: 4, 4: 6},
+ # 2: {4: 9},
+ # 3: {"t": 9},
+ # 4: {3: 5, "t": 10},
+ # "s": {1: 10, 2: 9},
+ # "t": {},
+ # }
+
+ compare_flows_and_cuts(G, "s", "t", 19)
+
+ def test_optional_capacity(self):
+ # Test optional capacity parameter.
+ G = nx.DiGraph()
+ G.add_edge("x", "a", spam=3.0)
+ G.add_edge("x", "b", spam=1.0)
+ G.add_edge("a", "c", spam=3.0)
+ G.add_edge("b", "c", spam=5.0)
+ G.add_edge("b", "d", spam=4.0)
+ G.add_edge("d", "e", spam=2.0)
+ G.add_edge("c", "y", spam=2.0)
+ G.add_edge("e", "y", spam=3.0)
+
+ # solution flows
+ # {
+ # "x": {"a": 2.0, "b": 1.0},
+ # "a": {"c": 2.0},
+ # "b": {"c": 0, "d": 1.0},
+ # "c": {"y": 2.0},
+ # "d": {"e": 1.0},
+ # "e": {"y": 1.0},
+ # "y": {},
+ # }
+ solnValue = 3.0
+ s = "x"
+ t = "y"
+
+ compare_flows_and_cuts(G, s, t, solnValue, capacity="spam")
+
+ def test_digraph_infcap_edges(self):
+ # DiGraph with infinite capacity edges
+ G = nx.DiGraph()
+ G.add_edge("s", "a")
+ G.add_edge("s", "b", capacity=30)
+ G.add_edge("a", "c", capacity=25)
+ G.add_edge("b", "c", capacity=12)
+ G.add_edge("a", "t", capacity=60)
+ G.add_edge("c", "t")
+
+ # H
+ # {
+ # "s": {"a": 85, "b": 12},
+ # "a": {"c": 25, "t": 60},
+ # "b": {"c": 12},
+ # "c": {"t": 37},
+ # "t": {},
+ # }
+
+ compare_flows_and_cuts(G, "s", "t", 97)
+
+ # DiGraph with infinite capacity digon
+ G = nx.DiGraph()
+ G.add_edge("s", "a", capacity=85)
+ G.add_edge("s", "b", capacity=30)
+ G.add_edge("a", "c")
+ G.add_edge("c", "a")
+ G.add_edge("b", "c", capacity=12)
+ G.add_edge("a", "t", capacity=60)
+ G.add_edge("c", "t", capacity=37)
+
+ # H
+ # {
+ # "s": {"a": 85, "b": 12},
+ # "a": {"c": 25, "t": 60},
+ # "c": {"a": 0, "t": 37},
+ # "b": {"c": 12},
+ # "t": {},
+ # }
+
+ compare_flows_and_cuts(G, "s", "t", 97)
+
+ def test_digraph_infcap_path(self):
+ # Graph with infinite capacity (s, t)-path
+ G = nx.DiGraph()
+ G.add_edge("s", "a")
+ G.add_edge("s", "b", capacity=30)
+ G.add_edge("a", "c")
+ G.add_edge("b", "c", capacity=12)
+ G.add_edge("a", "t", capacity=60)
+ G.add_edge("c", "t")
+
+ for flow_func in all_funcs:
+ pytest.raises(nx.NetworkXUnbounded, flow_func, G, "s", "t")
+
+ def test_graph_infcap_edges(self):
+ # Undirected graph with infinite capacity edges
+ G = nx.Graph()
+ G.add_edge("s", "a")
+ G.add_edge("s", "b", capacity=30)
+ G.add_edge("a", "c", capacity=25)
+ G.add_edge("b", "c", capacity=12)
+ G.add_edge("a", "t", capacity=60)
+ G.add_edge("c", "t")
+
+ # H
+ # {
+ # "s": {"a": 85, "b": 12},
+ # "a": {"c": 25, "s": 85, "t": 60},
+ # "b": {"c": 12, "s": 12},
+ # "c": {"a": 25, "b": 12, "t": 37},
+ # "t": {"a": 60, "c": 37},
+ # }
+
+ compare_flows_and_cuts(G, "s", "t", 97)
+
+ def test_digraph5(self):
+ # From ticket #429 by mfrasca.
+ G = nx.DiGraph()
+ G.add_edge("s", "a", capacity=2)
+ G.add_edge("s", "b", capacity=2)
+ G.add_edge("a", "b", capacity=5)
+ G.add_edge("a", "t", capacity=1)
+ G.add_edge("b", "a", capacity=1)
+ G.add_edge("b", "t", capacity=3)
+ # flow solution
+ # {
+ # "a": {"b": 1, "t": 1},
+ # "b": {"a": 0, "t": 3},
+ # "s": {"a": 2, "b": 2},
+ # "t": {},
+ # }
+ compare_flows_and_cuts(G, "s", "t", 4)
+
+ def test_disconnected(self):
+ G = nx.Graph()
+ G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight="capacity")
+ G.remove_node(1)
+ assert nx.maximum_flow_value(G, 0, 3) == 0
+ # flow solution
+ # {0: {}, 2: {3: 0}, 3: {2: 0}}
+ compare_flows_and_cuts(G, 0, 3, 0)
+
+ def test_source_target_not_in_graph(self):
+ G = nx.Graph()
+ G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight="capacity")
+ G.remove_node(0)
+ for flow_func in all_funcs:
+ pytest.raises(nx.NetworkXError, flow_func, G, 0, 3)
+ G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight="capacity")
+ G.remove_node(3)
+ for flow_func in all_funcs:
+ pytest.raises(nx.NetworkXError, flow_func, G, 0, 3)
+
+ def test_source_target_coincide(self):
+ G = nx.Graph()
+ G.add_node(0)
+ for flow_func in all_funcs:
+ pytest.raises(nx.NetworkXError, flow_func, G, 0, 0)
+
+ def test_multigraphs_raise(self):
+ G = nx.MultiGraph()
+ M = nx.MultiDiGraph()
+ G.add_edges_from([(0, 1), (1, 0)], capacity=True)
+ for flow_func in all_funcs:
+ pytest.raises(nx.NetworkXError, flow_func, G, 0, 0)
+
+
+class TestMaxFlowMinCutInterface:
+ def setup_method(self):
+ 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)
+ self.G = G
+ H = nx.DiGraph()
+ H.add_edge(0, 1, capacity=1.0)
+ H.add_edge(1, 2, capacity=1.0)
+ self.H = H
+
+ def test_flow_func_not_callable(self):
+ elements = ["this_should_be_callable", 10, {1, 2, 3}]
+ G = nx.Graph()
+ G.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1)], weight="capacity")
+ for flow_func in interface_funcs:
+ for element in elements:
+ pytest.raises(nx.NetworkXError, flow_func, G, 0, 1, flow_func=element)
+ pytest.raises(nx.NetworkXError, flow_func, G, 0, 1, flow_func=element)
+
+ def test_flow_func_parameters(self):
+ G = self.G
+ fv = 3.0
+ for interface_func in interface_funcs:
+ for flow_func in flow_funcs:
+ errmsg = (
+ f"Assertion failed in function: {flow_func.__name__} "
+ f"in interface {interface_func.__name__}"
+ )
+ result = interface_func(G, "x", "y", flow_func=flow_func)
+ if interface_func in max_min_funcs:
+ result = result[0]
+ assert fv == result, errmsg
+
+ def test_minimum_cut_no_cutoff(self):
+ G = self.G
+ pytest.raises(
+ nx.NetworkXError,
+ nx.minimum_cut,
+ G,
+ "x",
+ "y",
+ flow_func=preflow_push,
+ cutoff=1.0,
+ )
+ pytest.raises(
+ nx.NetworkXError,
+ nx.minimum_cut_value,
+ G,
+ "x",
+ "y",
+ flow_func=preflow_push,
+ cutoff=1.0,
+ )
+
+ def test_kwargs(self):
+ G = self.H
+ fv = 1.0
+ to_test = (
+ (shortest_augmenting_path, {"two_phase": True}),
+ (preflow_push, {"global_relabel_freq": 5}),
+ )
+ for interface_func in interface_funcs:
+ for flow_func, kwargs in to_test:
+ errmsg = (
+ f"Assertion failed in function: {flow_func.__name__} "
+ f"in interface {interface_func.__name__}"
+ )
+ result = interface_func(G, 0, 2, flow_func=flow_func, **kwargs)
+ if interface_func in max_min_funcs:
+ result = result[0]
+ assert fv == result, errmsg
+
+ def test_kwargs_default_flow_func(self):
+ G = self.H
+ for interface_func in interface_funcs:
+ pytest.raises(
+ nx.NetworkXError, interface_func, G, 0, 1, global_relabel_freq=2
+ )
+
+ def test_reusing_residual(self):
+ G = self.G
+ fv = 3.0
+ s, t = "x", "y"
+ R = build_residual_network(G, "capacity")
+ for interface_func in interface_funcs:
+ for flow_func in flow_funcs:
+ errmsg = (
+ f"Assertion failed in function: {flow_func.__name__} "
+ f"in interface {interface_func.__name__}"
+ )
+ for i in range(3):
+ result = interface_func(
+ G, "x", "y", flow_func=flow_func, residual=R
+ )
+ if interface_func in max_min_funcs:
+ result = result[0]
+ assert fv == result, errmsg
+
+
+# Tests specific to one algorithm
+def test_preflow_push_global_relabel_freq():
+ G = nx.DiGraph()
+ G.add_edge(1, 2, capacity=1)
+ R = preflow_push(G, 1, 2, global_relabel_freq=None)
+ assert R.graph["flow_value"] == 1
+ pytest.raises(nx.NetworkXError, preflow_push, G, 1, 2, global_relabel_freq=-1)
+
+
+def test_preflow_push_makes_enough_space():
+ # From ticket #1542
+ G = nx.DiGraph()
+ nx.add_path(G, [0, 1, 3], capacity=1)
+ nx.add_path(G, [1, 2, 3], capacity=1)
+ R = preflow_push(G, 0, 3, value_only=False)
+ assert R.graph["flow_value"] == 1
+
+
+def test_shortest_augmenting_path_two_phase():
+ k = 5
+ p = 1000
+ G = nx.DiGraph()
+ for i in range(k):
+ G.add_edge("s", (i, 0), capacity=1)
+ nx.add_path(G, ((i, j) for j in range(p)), capacity=1)
+ G.add_edge((i, p - 1), "t", capacity=1)
+ R = shortest_augmenting_path(G, "s", "t", two_phase=True)
+ assert R.graph["flow_value"] == k
+ R = shortest_augmenting_path(G, "s", "t", two_phase=False)
+ assert R.graph["flow_value"] == k
+
+
+class TestCutoff:
+ def test_cutoff(self):
+ k = 5
+ p = 1000
+ G = nx.DiGraph()
+ for i in range(k):
+ G.add_edge("s", (i, 0), capacity=2)
+ nx.add_path(G, ((i, j) for j in range(p)), capacity=2)
+ G.add_edge((i, p - 1), "t", capacity=2)
+ R = shortest_augmenting_path(G, "s", "t", two_phase=True, cutoff=k)
+ assert k <= R.graph["flow_value"] <= (2 * k)
+ R = shortest_augmenting_path(G, "s", "t", two_phase=False, cutoff=k)
+ assert k <= R.graph["flow_value"] <= (2 * k)
+ R = edmonds_karp(G, "s", "t", cutoff=k)
+ assert k <= R.graph["flow_value"] <= (2 * k)
+ R = dinitz(G, "s", "t", cutoff=k)
+ assert k <= R.graph["flow_value"] <= (2 * k)
+ R = boykov_kolmogorov(G, "s", "t", cutoff=k)
+ assert k <= R.graph["flow_value"] <= (2 * k)
+
+ def test_complete_graph_cutoff(self):
+ G = nx.complete_graph(5)
+ nx.set_edge_attributes(G, {(u, v): 1 for u, v in G.edges()}, "capacity")
+ for flow_func in [
+ shortest_augmenting_path,
+ edmonds_karp,
+ dinitz,
+ boykov_kolmogorov,
+ ]:
+ for cutoff in [3, 2, 1]:
+ result = nx.maximum_flow_value(
+ G, 0, 4, flow_func=flow_func, cutoff=cutoff
+ )
+ assert cutoff == result, f"cutoff error in {flow_func.__name__}"
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow_large_graph.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow_large_graph.py
new file mode 100644
index 00000000..b395cbc8
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_maxflow_large_graph.py
@@ -0,0 +1,156 @@
+"""Maximum flow algorithms test suite on large graphs."""
+
+import bz2
+import importlib.resources
+import os
+import pickle
+
+import pytest
+
+import networkx as nx
+from networkx.algorithms.flow import (
+ boykov_kolmogorov,
+ build_flow_dict,
+ build_residual_network,
+ dinitz,
+ edmonds_karp,
+ preflow_push,
+ shortest_augmenting_path,
+)
+
+flow_funcs = [
+ boykov_kolmogorov,
+ dinitz,
+ edmonds_karp,
+ preflow_push,
+ shortest_augmenting_path,
+]
+
+
+def gen_pyramid(N):
+ # This graph admits a flow of value 1 for which every arc is at
+ # capacity (except the arcs incident to the sink which have
+ # infinite capacity).
+ G = nx.DiGraph()
+
+ for i in range(N - 1):
+ cap = 1.0 / (i + 2)
+ for j in range(i + 1):
+ G.add_edge((i, j), (i + 1, j), capacity=cap)
+ cap = 1.0 / (i + 1) - cap
+ G.add_edge((i, j), (i + 1, j + 1), capacity=cap)
+ cap = 1.0 / (i + 2) - cap
+
+ for j in range(N):
+ G.add_edge((N - 1, j), "t")
+
+ return G
+
+
+def read_graph(name):
+ fname = (
+ importlib.resources.files("networkx.algorithms.flow.tests")
+ / f"{name}.gpickle.bz2"
+ )
+
+ with bz2.BZ2File(fname, "rb") as f:
+ G = pickle.load(f)
+ return G
+
+
+def validate_flows(G, s, t, soln_value, R, flow_func):
+ flow_value = R.graph["flow_value"]
+ flow_dict = build_flow_dict(G, R)
+ errmsg = f"Assertion failed in function: {flow_func.__name__}"
+ assert soln_value == flow_value, errmsg
+ assert set(G) == set(flow_dict), errmsg
+ for u in G:
+ assert set(G[u]) == set(flow_dict[u]), errmsg
+ excess = {u: 0 for u in flow_dict}
+ for u in flow_dict:
+ for v, flow in flow_dict[u].items():
+ assert flow <= G[u][v].get("capacity", float("inf")), errmsg
+ assert flow >= 0, errmsg
+ excess[u] -= flow
+ excess[v] += flow
+ for u, exc in excess.items():
+ if u == s:
+ assert exc == -soln_value, errmsg
+ elif u == t:
+ assert exc == soln_value, errmsg
+ else:
+ assert exc == 0, errmsg
+
+
+class TestMaxflowLargeGraph:
+ def test_complete_graph(self):
+ N = 50
+ G = nx.complete_graph(N)
+ nx.set_edge_attributes(G, 5, "capacity")
+ R = build_residual_network(G, "capacity")
+ kwargs = {"residual": R}
+
+ for flow_func in flow_funcs:
+ kwargs["flow_func"] = flow_func
+ errmsg = f"Assertion failed in function: {flow_func.__name__}"
+ flow_value = nx.maximum_flow_value(G, 1, 2, **kwargs)
+ assert flow_value == 5 * (N - 1), errmsg
+
+ def test_pyramid(self):
+ N = 10
+ # N = 100 # this gives a graph with 5051 nodes
+ G = gen_pyramid(N)
+ R = build_residual_network(G, "capacity")
+ kwargs = {"residual": R}
+
+ for flow_func in flow_funcs:
+ kwargs["flow_func"] = flow_func
+ errmsg = f"Assertion failed in function: {flow_func.__name__}"
+ flow_value = nx.maximum_flow_value(G, (0, 0), "t", **kwargs)
+ assert flow_value == pytest.approx(1.0, abs=1e-7)
+
+ def test_gl1(self):
+ G = read_graph("gl1")
+ s = 1
+ t = len(G)
+ R = build_residual_network(G, "capacity")
+ kwargs = {"residual": R}
+
+ # do one flow_func to save time
+ flow_func = flow_funcs[0]
+ validate_flows(G, s, t, 156545, flow_func(G, s, t, **kwargs), flow_func)
+
+ # for flow_func in flow_funcs:
+ # validate_flows(G, s, t, 156545, flow_func(G, s, t, **kwargs),
+ # flow_func)
+
+ @pytest.mark.slow
+ def test_gw1(self):
+ G = read_graph("gw1")
+ s = 1
+ t = len(G)
+ R = build_residual_network(G, "capacity")
+ kwargs = {"residual": R}
+
+ for flow_func in flow_funcs:
+ validate_flows(G, s, t, 1202018, flow_func(G, s, t, **kwargs), flow_func)
+
+ def test_wlm3(self):
+ G = read_graph("wlm3")
+ s = 1
+ t = len(G)
+ R = build_residual_network(G, "capacity")
+ kwargs = {"residual": R}
+
+ # do one flow_func to save time
+ flow_func = flow_funcs[0]
+ validate_flows(G, s, t, 11875108, flow_func(G, s, t, **kwargs), flow_func)
+
+ # for flow_func in flow_funcs:
+ # validate_flows(G, s, t, 11875108, flow_func(G, s, t, **kwargs),
+ # flow_func)
+
+ def test_preflow_push_global_relabel(self):
+ G = read_graph("gw1")
+ R = preflow_push(G, 1, len(G), global_relabel_freq=50)
+ assert R.graph["flow_value"] == 1202018
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_mincost.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_mincost.py
new file mode 100644
index 00000000..5b1794b1
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_mincost.py
@@ -0,0 +1,476 @@
+import bz2
+import importlib.resources
+import os
+import pickle
+
+import pytest
+
+import networkx as nx
+
+
+class TestMinCostFlow:
+ def test_simple_digraph(self):
+ G = nx.DiGraph()
+ G.add_node("a", demand=-5)
+ G.add_node("d", demand=5)
+ G.add_edge("a", "b", weight=3, capacity=4)
+ G.add_edge("a", "c", weight=6, capacity=10)
+ G.add_edge("b", "d", weight=1, capacity=9)
+ G.add_edge("c", "d", weight=2, capacity=5)
+ flowCost, H = nx.network_simplex(G)
+ soln = {"a": {"b": 4, "c": 1}, "b": {"d": 4}, "c": {"d": 1}, "d": {}}
+ assert flowCost == 24
+ assert nx.min_cost_flow_cost(G) == 24
+ assert H == soln
+ assert nx.min_cost_flow(G) == soln
+ assert nx.cost_of_flow(G, H) == 24
+
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == 24
+ assert nx.cost_of_flow(G, H) == 24
+ assert H == soln
+
+ def test_negcycle_infcap(self):
+ G = nx.DiGraph()
+ G.add_node("s", demand=-5)
+ G.add_node("t", demand=5)
+ G.add_edge("s", "a", weight=1, capacity=3)
+ G.add_edge("a", "b", weight=3)
+ G.add_edge("c", "a", weight=-6)
+ G.add_edge("b", "d", weight=1)
+ G.add_edge("d", "c", weight=-2)
+ G.add_edge("d", "t", weight=1, capacity=3)
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
+
+ def test_sum_demands_not_zero(self):
+ G = nx.DiGraph()
+ G.add_node("s", demand=-5)
+ G.add_node("t", demand=4)
+ G.add_edge("s", "a", weight=1, capacity=3)
+ G.add_edge("a", "b", weight=3)
+ G.add_edge("a", "c", weight=-6)
+ G.add_edge("b", "d", weight=1)
+ G.add_edge("c", "d", weight=-2)
+ G.add_edge("d", "t", weight=1, capacity=3)
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
+
+ def test_no_flow_satisfying_demands(self):
+ G = nx.DiGraph()
+ G.add_node("s", demand=-5)
+ G.add_node("t", demand=5)
+ G.add_edge("s", "a", weight=1, capacity=3)
+ G.add_edge("a", "b", weight=3)
+ G.add_edge("a", "c", weight=-6)
+ G.add_edge("b", "d", weight=1)
+ G.add_edge("c", "d", weight=-2)
+ G.add_edge("d", "t", weight=1, capacity=3)
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
+
+ def test_transshipment(self):
+ G = nx.DiGraph()
+ G.add_node("a", demand=1)
+ G.add_node("b", demand=-2)
+ G.add_node("c", demand=-2)
+ G.add_node("d", demand=3)
+ G.add_node("e", demand=-4)
+ G.add_node("f", demand=-4)
+ G.add_node("g", demand=3)
+ G.add_node("h", demand=2)
+ G.add_node("r", demand=3)
+ G.add_edge("a", "c", weight=3)
+ G.add_edge("r", "a", weight=2)
+ G.add_edge("b", "a", weight=9)
+ G.add_edge("r", "c", weight=0)
+ G.add_edge("b", "r", weight=-6)
+ G.add_edge("c", "d", weight=5)
+ G.add_edge("e", "r", weight=4)
+ G.add_edge("e", "f", weight=3)
+ G.add_edge("h", "b", weight=4)
+ G.add_edge("f", "d", weight=7)
+ G.add_edge("f", "h", weight=12)
+ G.add_edge("g", "d", weight=12)
+ G.add_edge("f", "g", weight=-1)
+ G.add_edge("h", "g", weight=-10)
+ flowCost, H = nx.network_simplex(G)
+ soln = {
+ "a": {"c": 0},
+ "b": {"a": 0, "r": 2},
+ "c": {"d": 3},
+ "d": {},
+ "e": {"r": 3, "f": 1},
+ "f": {"d": 0, "g": 3, "h": 2},
+ "g": {"d": 0},
+ "h": {"b": 0, "g": 0},
+ "r": {"a": 1, "c": 1},
+ }
+ assert flowCost == 41
+ assert nx.min_cost_flow_cost(G) == 41
+ assert H == soln
+ assert nx.min_cost_flow(G) == soln
+ assert nx.cost_of_flow(G, H) == 41
+
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == 41
+ assert nx.cost_of_flow(G, H) == 41
+ assert H == soln
+
+ def test_max_flow_min_cost(self):
+ G = nx.DiGraph()
+ G.add_edge("s", "a", bandwidth=6)
+ G.add_edge("s", "c", bandwidth=10, cost=10)
+ G.add_edge("a", "b", cost=6)
+ G.add_edge("b", "d", bandwidth=8, cost=7)
+ G.add_edge("c", "d", cost=10)
+ G.add_edge("d", "t", bandwidth=5, cost=5)
+ soln = {
+ "s": {"a": 5, "c": 0},
+ "a": {"b": 5},
+ "b": {"d": 5},
+ "c": {"d": 0},
+ "d": {"t": 5},
+ "t": {},
+ }
+ flow = nx.max_flow_min_cost(G, "s", "t", capacity="bandwidth", weight="cost")
+ assert flow == soln
+ assert nx.cost_of_flow(G, flow, weight="cost") == 90
+
+ G.add_edge("t", "s", cost=-100)
+ flowCost, flow = nx.capacity_scaling(G, capacity="bandwidth", weight="cost")
+ G.remove_edge("t", "s")
+ assert flowCost == -410
+ assert flow["t"]["s"] == 5
+ del flow["t"]["s"]
+ assert flow == soln
+ assert nx.cost_of_flow(G, flow, weight="cost") == 90
+
+ def test_digraph1(self):
+ # From Bradley, S. P., Hax, A. C. and Magnanti, T. L. Applied
+ # Mathematical Programming. Addison-Wesley, 1977.
+ G = nx.DiGraph()
+ G.add_node(1, demand=-20)
+ G.add_node(4, demand=5)
+ G.add_node(5, demand=15)
+ G.add_edges_from(
+ [
+ (1, 2, {"capacity": 15, "weight": 4}),
+ (1, 3, {"capacity": 8, "weight": 4}),
+ (2, 3, {"weight": 2}),
+ (2, 4, {"capacity": 4, "weight": 2}),
+ (2, 5, {"capacity": 10, "weight": 6}),
+ (3, 4, {"capacity": 15, "weight": 1}),
+ (3, 5, {"capacity": 5, "weight": 3}),
+ (4, 5, {"weight": 2}),
+ (5, 3, {"capacity": 4, "weight": 1}),
+ ]
+ )
+ flowCost, H = nx.network_simplex(G)
+ soln = {
+ 1: {2: 12, 3: 8},
+ 2: {3: 8, 4: 4, 5: 0},
+ 3: {4: 11, 5: 5},
+ 4: {5: 10},
+ 5: {3: 0},
+ }
+ assert flowCost == 150
+ assert nx.min_cost_flow_cost(G) == 150
+ assert H == soln
+ assert nx.min_cost_flow(G) == soln
+ assert nx.cost_of_flow(G, H) == 150
+
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == 150
+ assert H == soln
+ assert nx.cost_of_flow(G, H) == 150
+
+ def test_digraph2(self):
+ # Example from ticket #430 from mfrasca. Original source:
+ # http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/mincost.4up.pdf, slide 11.
+ G = nx.DiGraph()
+ G.add_edge("s", 1, capacity=12)
+ G.add_edge("s", 2, capacity=6)
+ G.add_edge("s", 3, capacity=14)
+ G.add_edge(1, 2, capacity=11, weight=4)
+ G.add_edge(2, 3, capacity=9, weight=6)
+ G.add_edge(1, 4, capacity=5, weight=5)
+ G.add_edge(1, 5, capacity=2, weight=12)
+ G.add_edge(2, 5, capacity=4, weight=4)
+ G.add_edge(2, 6, capacity=2, weight=6)
+ G.add_edge(3, 6, capacity=31, weight=3)
+ G.add_edge(4, 5, capacity=18, weight=4)
+ G.add_edge(5, 6, capacity=9, weight=5)
+ G.add_edge(4, "t", capacity=3)
+ G.add_edge(5, "t", capacity=7)
+ G.add_edge(6, "t", capacity=22)
+ flow = nx.max_flow_min_cost(G, "s", "t")
+ soln = {
+ 1: {2: 6, 4: 5, 5: 1},
+ 2: {3: 6, 5: 4, 6: 2},
+ 3: {6: 20},
+ 4: {5: 2, "t": 3},
+ 5: {6: 0, "t": 7},
+ 6: {"t": 22},
+ "s": {1: 12, 2: 6, 3: 14},
+ "t": {},
+ }
+ assert flow == soln
+
+ G.add_edge("t", "s", weight=-100)
+ flowCost, flow = nx.capacity_scaling(G)
+ G.remove_edge("t", "s")
+ assert flow["t"]["s"] == 32
+ assert flowCost == -3007
+ del flow["t"]["s"]
+ assert flow == soln
+ assert nx.cost_of_flow(G, flow) == 193
+
+ def test_digraph3(self):
+ """Combinatorial Optimization: Algorithms and Complexity,
+ Papadimitriou Steiglitz at page 140 has an example, 7.1, but that
+ admits multiple solutions, so I alter it a bit. From ticket #430
+ by mfrasca."""
+
+ G = nx.DiGraph()
+ G.add_edge("s", "a")
+ G["s"]["a"].update({0: 2, 1: 4})
+ G.add_edge("s", "b")
+ G["s"]["b"].update({0: 2, 1: 1})
+ G.add_edge("a", "b")
+ G["a"]["b"].update({0: 5, 1: 2})
+ G.add_edge("a", "t")
+ G["a"]["t"].update({0: 1, 1: 5})
+ G.add_edge("b", "a")
+ G["b"]["a"].update({0: 1, 1: 3})
+ G.add_edge("b", "t")
+ G["b"]["t"].update({0: 3, 1: 2})
+
+ "PS.ex.7.1: testing main function"
+ sol = nx.max_flow_min_cost(G, "s", "t", capacity=0, weight=1)
+ flow = sum(v for v in sol["s"].values())
+ assert 4 == flow
+ assert 23 == nx.cost_of_flow(G, sol, weight=1)
+ assert sol["s"] == {"a": 2, "b": 2}
+ assert sol["a"] == {"b": 1, "t": 1}
+ assert sol["b"] == {"a": 0, "t": 3}
+ assert sol["t"] == {}
+
+ G.add_edge("t", "s")
+ G["t"]["s"].update({1: -100})
+ flowCost, sol = nx.capacity_scaling(G, capacity=0, weight=1)
+ G.remove_edge("t", "s")
+ flow = sum(v for v in sol["s"].values())
+ assert 4 == flow
+ assert sol["t"]["s"] == 4
+ assert flowCost == -377
+ del sol["t"]["s"]
+ assert sol["s"] == {"a": 2, "b": 2}
+ assert sol["a"] == {"b": 1, "t": 1}
+ assert sol["b"] == {"a": 0, "t": 3}
+ assert sol["t"] == {}
+ assert nx.cost_of_flow(G, sol, weight=1) == 23
+
+ def test_zero_capacity_edges(self):
+ """Address issue raised in ticket #617 by arv."""
+ G = nx.DiGraph()
+ G.add_edges_from(
+ [
+ (1, 2, {"capacity": 1, "weight": 1}),
+ (1, 5, {"capacity": 1, "weight": 1}),
+ (2, 3, {"capacity": 0, "weight": 1}),
+ (2, 5, {"capacity": 1, "weight": 1}),
+ (5, 3, {"capacity": 2, "weight": 1}),
+ (5, 4, {"capacity": 0, "weight": 1}),
+ (3, 4, {"capacity": 2, "weight": 1}),
+ ]
+ )
+ G.nodes[1]["demand"] = -1
+ G.nodes[2]["demand"] = -1
+ G.nodes[4]["demand"] = 2
+
+ flowCost, H = nx.network_simplex(G)
+ soln = {1: {2: 0, 5: 1}, 2: {3: 0, 5: 1}, 3: {4: 2}, 4: {}, 5: {3: 2, 4: 0}}
+ assert flowCost == 6
+ assert nx.min_cost_flow_cost(G) == 6
+ assert H == soln
+ assert nx.min_cost_flow(G) == soln
+ assert nx.cost_of_flow(G, H) == 6
+
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == 6
+ assert H == soln
+ assert nx.cost_of_flow(G, H) == 6
+
+ def test_digon(self):
+ """Check if digons are handled properly. Taken from ticket
+ #618 by arv."""
+ nodes = [(1, {}), (2, {"demand": -4}), (3, {"demand": 4})]
+ edges = [
+ (1, 2, {"capacity": 3, "weight": 600000}),
+ (2, 1, {"capacity": 2, "weight": 0}),
+ (2, 3, {"capacity": 5, "weight": 714285}),
+ (3, 2, {"capacity": 2, "weight": 0}),
+ ]
+ G = nx.DiGraph(edges)
+ G.add_nodes_from(nodes)
+ flowCost, H = nx.network_simplex(G)
+ soln = {1: {2: 0}, 2: {1: 0, 3: 4}, 3: {2: 0}}
+ assert flowCost == 2857140
+ assert nx.min_cost_flow_cost(G) == 2857140
+ assert H == soln
+ assert nx.min_cost_flow(G) == soln
+ assert nx.cost_of_flow(G, H) == 2857140
+
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == 2857140
+ assert H == soln
+ assert nx.cost_of_flow(G, H) == 2857140
+
+ def test_deadend(self):
+ """Check if one-node cycles are handled properly. Taken from ticket
+ #2906 from @sshraven."""
+ G = nx.DiGraph()
+
+ G.add_nodes_from(range(5), demand=0)
+ G.nodes[4]["demand"] = -13
+ G.nodes[3]["demand"] = 13
+
+ G.add_edges_from([(0, 2), (0, 3), (2, 1)], capacity=20, weight=0.1)
+ pytest.raises(nx.NetworkXUnfeasible, nx.min_cost_flow, G)
+
+ def test_infinite_capacity_neg_digon(self):
+ """An infinite capacity negative cost digon results in an unbounded
+ instance."""
+ nodes = [(1, {}), (2, {"demand": -4}), (3, {"demand": 4})]
+ edges = [
+ (1, 2, {"weight": -600}),
+ (2, 1, {"weight": 0}),
+ (2, 3, {"capacity": 5, "weight": 714285}),
+ (3, 2, {"capacity": 2, "weight": 0}),
+ ]
+ G = nx.DiGraph(edges)
+ G.add_nodes_from(nodes)
+ pytest.raises(nx.NetworkXUnbounded, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
+
+ def test_finite_capacity_neg_digon(self):
+ """The digon should receive the maximum amount of flow it can handle.
+ Taken from ticket #749 by @chuongdo."""
+ G = nx.DiGraph()
+ G.add_edge("a", "b", capacity=1, weight=-1)
+ G.add_edge("b", "a", capacity=1, weight=-1)
+ min_cost = -2
+ assert nx.min_cost_flow_cost(G) == min_cost
+
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == -2
+ assert H == {"a": {"b": 1}, "b": {"a": 1}}
+ assert nx.cost_of_flow(G, H) == -2
+
+ def test_multidigraph(self):
+ """Multidigraphs are acceptable."""
+ G = nx.MultiDiGraph()
+ G.add_weighted_edges_from([(1, 2, 1), (2, 3, 2)], weight="capacity")
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == 0
+ assert H == {1: {2: {0: 0}}, 2: {3: {0: 0}}, 3: {}}
+
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == 0
+ assert H == {1: {2: {0: 0}}, 2: {3: {0: 0}}, 3: {}}
+
+ def test_negative_selfloops(self):
+ """Negative selfloops should cause an exception if uncapacitated and
+ always be saturated otherwise.
+ """
+ G = nx.DiGraph()
+ G.add_edge(1, 1, weight=-1)
+ pytest.raises(nx.NetworkXUnbounded, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
+ G[1][1]["capacity"] = 2
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == -2
+ assert H == {1: {1: 2}}
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == -2
+ assert H == {1: {1: 2}}
+
+ G = nx.MultiDiGraph()
+ G.add_edge(1, 1, "x", weight=-1)
+ G.add_edge(1, 1, "y", weight=1)
+ pytest.raises(nx.NetworkXUnbounded, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnbounded, nx.capacity_scaling, G)
+ G[1][1]["x"]["capacity"] = 2
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == -2
+ assert H == {1: {1: {"x": 2, "y": 0}}}
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == -2
+ assert H == {1: {1: {"x": 2, "y": 0}}}
+
+ def test_bone_shaped(self):
+ # From #1283
+ G = nx.DiGraph()
+ G.add_node(0, demand=-4)
+ G.add_node(1, demand=2)
+ G.add_node(2, demand=2)
+ G.add_node(3, demand=4)
+ G.add_node(4, demand=-2)
+ G.add_node(5, demand=-2)
+ G.add_edge(0, 1, capacity=4)
+ G.add_edge(0, 2, capacity=4)
+ G.add_edge(4, 3, capacity=4)
+ G.add_edge(5, 3, capacity=4)
+ G.add_edge(0, 3, capacity=0)
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == 0
+ assert H == {0: {1: 2, 2: 2, 3: 0}, 1: {}, 2: {}, 3: {}, 4: {3: 2}, 5: {3: 2}}
+ flowCost, H = nx.capacity_scaling(G)
+ assert flowCost == 0
+ assert H == {0: {1: 2, 2: 2, 3: 0}, 1: {}, 2: {}, 3: {}, 4: {3: 2}, 5: {3: 2}}
+
+ def test_exceptions(self):
+ G = nx.Graph()
+ pytest.raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXNotImplemented, nx.capacity_scaling, G)
+ G = nx.MultiGraph()
+ pytest.raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXNotImplemented, nx.capacity_scaling, G)
+ G = nx.DiGraph()
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+ # pytest.raises(nx.NetworkXError, nx.capacity_scaling, G)
+ G.add_node(0, demand=float("inf"))
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
+ G.nodes[0]["demand"] = 0
+ G.add_node(1, demand=0)
+ G.add_edge(0, 1, weight=-float("inf"))
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+ pytest.raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
+ G[0][1]["weight"] = 0
+ G.add_edge(0, 0, weight=float("inf"))
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+ # pytest.raises(nx.NetworkXError, nx.capacity_scaling, G)
+ G[0][0]["weight"] = 0
+ G[0][1]["capacity"] = -1
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+ # pytest.raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
+ G[0][1]["capacity"] = 0
+ G[0][0]["capacity"] = -1
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+ # pytest.raises(nx.NetworkXUnfeasible, nx.capacity_scaling, G)
+
+ def test_large(self):
+ fname = (
+ importlib.resources.files("networkx.algorithms.flow.tests")
+ / "netgen-2.gpickle.bz2"
+ )
+ with bz2.BZ2File(fname, "rb") as f:
+ G = pickle.load(f)
+ flowCost, flowDict = nx.network_simplex(G)
+ assert 6749969302 == flowCost
+ assert 6749969302 == nx.cost_of_flow(G, flowDict)
+ flowCost, flowDict = nx.capacity_scaling(G)
+ assert 6749969302 == flowCost
+ assert 6749969302 == nx.cost_of_flow(G, flowDict)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_networksimplex.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_networksimplex.py
new file mode 100644
index 00000000..5b3b5f6d
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/test_networksimplex.py
@@ -0,0 +1,387 @@
+import bz2
+import importlib.resources
+import os
+import pickle
+
+import pytest
+
+import networkx as nx
+
+
+@pytest.fixture
+def simple_flow_graph():
+ G = nx.DiGraph()
+ G.add_node("a", demand=0)
+ G.add_node("b", demand=-5)
+ G.add_node("c", demand=50000000)
+ G.add_node("d", demand=-49999995)
+ G.add_edge("a", "b", weight=3, capacity=4)
+ G.add_edge("a", "c", weight=6, capacity=10)
+ G.add_edge("b", "d", weight=1, capacity=9)
+ G.add_edge("c", "d", weight=2, capacity=5)
+ return G
+
+
+@pytest.fixture
+def simple_no_flow_graph():
+ G = nx.DiGraph()
+ G.add_node("s", demand=-5)
+ G.add_node("t", demand=5)
+ G.add_edge("s", "a", weight=1, capacity=3)
+ G.add_edge("a", "b", weight=3)
+ G.add_edge("a", "c", weight=-6)
+ G.add_edge("b", "d", weight=1)
+ G.add_edge("c", "d", weight=-2)
+ G.add_edge("d", "t", weight=1, capacity=3)
+ return G
+
+
+def get_flowcost_from_flowdict(G, flowDict):
+ """Returns flow cost calculated from flow dictionary"""
+ flowCost = 0
+ for u in flowDict:
+ for v in flowDict[u]:
+ flowCost += flowDict[u][v] * G[u][v]["weight"]
+ return flowCost
+
+
+def test_infinite_demand_raise(simple_flow_graph):
+ G = simple_flow_graph
+ inf = float("inf")
+ nx.set_node_attributes(G, {"a": {"demand": inf}})
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+
+
+def test_neg_infinite_demand_raise(simple_flow_graph):
+ G = simple_flow_graph
+ inf = float("inf")
+ nx.set_node_attributes(G, {"a": {"demand": -inf}})
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+
+
+def test_infinite_weight_raise(simple_flow_graph):
+ G = simple_flow_graph
+ inf = float("inf")
+ nx.set_edge_attributes(
+ G, {("a", "b"): {"weight": inf}, ("b", "d"): {"weight": inf}}
+ )
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
+
+
+def test_nonzero_net_demand_raise(simple_flow_graph):
+ G = simple_flow_graph
+ nx.set_node_attributes(G, {"b": {"demand": -4}})
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+
+
+def test_negative_capacity_raise(simple_flow_graph):
+ G = simple_flow_graph
+ nx.set_edge_attributes(G, {("a", "b"): {"weight": 1}, ("b", "d"): {"capacity": -9}})
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+
+
+def test_no_flow_satisfying_demands(simple_no_flow_graph):
+ G = simple_no_flow_graph
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+
+
+def test_sum_demands_not_zero(simple_no_flow_graph):
+ G = simple_no_flow_graph
+ nx.set_node_attributes(G, {"t": {"demand": 4}})
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+
+
+def test_google_or_tools_example():
+ """
+ https://developers.google.com/optimization/flow/mincostflow
+ """
+ G = nx.DiGraph()
+ start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4]
+ end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2]
+ capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
+ unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3]
+ supplies = [20, 0, 0, -5, -15]
+ answer = 150
+
+ for i in range(len(supplies)):
+ G.add_node(i, demand=(-1) * supplies[i]) # supplies are negative of demand
+
+ for i in range(len(start_nodes)):
+ G.add_edge(
+ start_nodes[i], end_nodes[i], weight=unit_costs[i], capacity=capacities[i]
+ )
+
+ flowCost, flowDict = nx.network_simplex(G)
+ assert flowCost == answer
+ assert flowCost == get_flowcost_from_flowdict(G, flowDict)
+
+
+def test_google_or_tools_example2():
+ """
+ https://developers.google.com/optimization/flow/mincostflow
+ """
+ G = nx.DiGraph()
+ start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4, 3]
+ end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2, 5]
+ capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5, 10]
+ unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3, 4]
+ supplies = [23, 0, 0, -5, -15, -3]
+ answer = 183
+
+ for i in range(len(supplies)):
+ G.add_node(i, demand=(-1) * supplies[i]) # supplies are negative of demand
+
+ for i in range(len(start_nodes)):
+ G.add_edge(
+ start_nodes[i], end_nodes[i], weight=unit_costs[i], capacity=capacities[i]
+ )
+
+ flowCost, flowDict = nx.network_simplex(G)
+ assert flowCost == answer
+ assert flowCost == get_flowcost_from_flowdict(G, flowDict)
+
+
+def test_large():
+ fname = (
+ importlib.resources.files("networkx.algorithms.flow.tests")
+ / "netgen-2.gpickle.bz2"
+ )
+
+ with bz2.BZ2File(fname, "rb") as f:
+ G = pickle.load(f)
+ flowCost, flowDict = nx.network_simplex(G)
+ assert 6749969302 == flowCost
+ assert 6749969302 == nx.cost_of_flow(G, flowDict)
+
+
+def test_simple_digraph():
+ G = nx.DiGraph()
+ G.add_node("a", demand=-5)
+ G.add_node("d", demand=5)
+ G.add_edge("a", "b", weight=3, capacity=4)
+ G.add_edge("a", "c", weight=6, capacity=10)
+ G.add_edge("b", "d", weight=1, capacity=9)
+ G.add_edge("c", "d", weight=2, capacity=5)
+ flowCost, H = nx.network_simplex(G)
+ soln = {"a": {"b": 4, "c": 1}, "b": {"d": 4}, "c": {"d": 1}, "d": {}}
+ assert flowCost == 24
+ assert nx.min_cost_flow_cost(G) == 24
+ assert H == soln
+
+
+def test_negcycle_infcap():
+ G = nx.DiGraph()
+ G.add_node("s", demand=-5)
+ G.add_node("t", demand=5)
+ G.add_edge("s", "a", weight=1, capacity=3)
+ G.add_edge("a", "b", weight=3)
+ G.add_edge("c", "a", weight=-6)
+ G.add_edge("b", "d", weight=1)
+ G.add_edge("d", "c", weight=-2)
+ G.add_edge("d", "t", weight=1, capacity=3)
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+
+
+def test_transshipment():
+ G = nx.DiGraph()
+ G.add_node("a", demand=1)
+ G.add_node("b", demand=-2)
+ G.add_node("c", demand=-2)
+ G.add_node("d", demand=3)
+ G.add_node("e", demand=-4)
+ G.add_node("f", demand=-4)
+ G.add_node("g", demand=3)
+ G.add_node("h", demand=2)
+ G.add_node("r", demand=3)
+ G.add_edge("a", "c", weight=3)
+ G.add_edge("r", "a", weight=2)
+ G.add_edge("b", "a", weight=9)
+ G.add_edge("r", "c", weight=0)
+ G.add_edge("b", "r", weight=-6)
+ G.add_edge("c", "d", weight=5)
+ G.add_edge("e", "r", weight=4)
+ G.add_edge("e", "f", weight=3)
+ G.add_edge("h", "b", weight=4)
+ G.add_edge("f", "d", weight=7)
+ G.add_edge("f", "h", weight=12)
+ G.add_edge("g", "d", weight=12)
+ G.add_edge("f", "g", weight=-1)
+ G.add_edge("h", "g", weight=-10)
+ flowCost, H = nx.network_simplex(G)
+ soln = {
+ "a": {"c": 0},
+ "b": {"a": 0, "r": 2},
+ "c": {"d": 3},
+ "d": {},
+ "e": {"r": 3, "f": 1},
+ "f": {"d": 0, "g": 3, "h": 2},
+ "g": {"d": 0},
+ "h": {"b": 0, "g": 0},
+ "r": {"a": 1, "c": 1},
+ }
+ assert flowCost == 41
+ assert H == soln
+
+
+def test_digraph1():
+ # From Bradley, S. P., Hax, A. C. and Magnanti, T. L. Applied
+ # Mathematical Programming. Addison-Wesley, 1977.
+ G = nx.DiGraph()
+ G.add_node(1, demand=-20)
+ G.add_node(4, demand=5)
+ G.add_node(5, demand=15)
+ G.add_edges_from(
+ [
+ (1, 2, {"capacity": 15, "weight": 4}),
+ (1, 3, {"capacity": 8, "weight": 4}),
+ (2, 3, {"weight": 2}),
+ (2, 4, {"capacity": 4, "weight": 2}),
+ (2, 5, {"capacity": 10, "weight": 6}),
+ (3, 4, {"capacity": 15, "weight": 1}),
+ (3, 5, {"capacity": 5, "weight": 3}),
+ (4, 5, {"weight": 2}),
+ (5, 3, {"capacity": 4, "weight": 1}),
+ ]
+ )
+ flowCost, H = nx.network_simplex(G)
+ soln = {
+ 1: {2: 12, 3: 8},
+ 2: {3: 8, 4: 4, 5: 0},
+ 3: {4: 11, 5: 5},
+ 4: {5: 10},
+ 5: {3: 0},
+ }
+ assert flowCost == 150
+ assert nx.min_cost_flow_cost(G) == 150
+ assert H == soln
+
+
+def test_zero_capacity_edges():
+ """Address issue raised in ticket #617 by arv."""
+ G = nx.DiGraph()
+ G.add_edges_from(
+ [
+ (1, 2, {"capacity": 1, "weight": 1}),
+ (1, 5, {"capacity": 1, "weight": 1}),
+ (2, 3, {"capacity": 0, "weight": 1}),
+ (2, 5, {"capacity": 1, "weight": 1}),
+ (5, 3, {"capacity": 2, "weight": 1}),
+ (5, 4, {"capacity": 0, "weight": 1}),
+ (3, 4, {"capacity": 2, "weight": 1}),
+ ]
+ )
+ G.nodes[1]["demand"] = -1
+ G.nodes[2]["demand"] = -1
+ G.nodes[4]["demand"] = 2
+
+ flowCost, H = nx.network_simplex(G)
+ soln = {1: {2: 0, 5: 1}, 2: {3: 0, 5: 1}, 3: {4: 2}, 4: {}, 5: {3: 2, 4: 0}}
+ assert flowCost == 6
+ assert nx.min_cost_flow_cost(G) == 6
+ assert H == soln
+
+
+def test_digon():
+ """Check if digons are handled properly. Taken from ticket
+ #618 by arv."""
+ nodes = [(1, {}), (2, {"demand": -4}), (3, {"demand": 4})]
+ edges = [
+ (1, 2, {"capacity": 3, "weight": 600000}),
+ (2, 1, {"capacity": 2, "weight": 0}),
+ (2, 3, {"capacity": 5, "weight": 714285}),
+ (3, 2, {"capacity": 2, "weight": 0}),
+ ]
+ G = nx.DiGraph(edges)
+ G.add_nodes_from(nodes)
+ flowCost, H = nx.network_simplex(G)
+ soln = {1: {2: 0}, 2: {1: 0, 3: 4}, 3: {2: 0}}
+ assert flowCost == 2857140
+
+
+def test_deadend():
+ """Check if one-node cycles are handled properly. Taken from ticket
+ #2906 from @sshraven."""
+ G = nx.DiGraph()
+
+ G.add_nodes_from(range(5), demand=0)
+ G.nodes[4]["demand"] = -13
+ G.nodes[3]["demand"] = 13
+
+ G.add_edges_from([(0, 2), (0, 3), (2, 1)], capacity=20, weight=0.1)
+ pytest.raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
+
+
+def test_infinite_capacity_neg_digon():
+ """An infinite capacity negative cost digon results in an unbounded
+ instance."""
+ nodes = [(1, {}), (2, {"demand": -4}), (3, {"demand": 4})]
+ edges = [
+ (1, 2, {"weight": -600}),
+ (2, 1, {"weight": 0}),
+ (2, 3, {"capacity": 5, "weight": 714285}),
+ (3, 2, {"capacity": 2, "weight": 0}),
+ ]
+ G = nx.DiGraph(edges)
+ G.add_nodes_from(nodes)
+ pytest.raises(nx.NetworkXUnbounded, nx.network_simplex, G)
+
+
+def test_multidigraph():
+ """Multidigraphs are acceptable."""
+ G = nx.MultiDiGraph()
+ G.add_weighted_edges_from([(1, 2, 1), (2, 3, 2)], weight="capacity")
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == 0
+ assert H == {1: {2: {0: 0}}, 2: {3: {0: 0}}, 3: {}}
+
+
+def test_negative_selfloops():
+ """Negative selfloops should cause an exception if uncapacitated and
+ always be saturated otherwise.
+ """
+ G = nx.DiGraph()
+ G.add_edge(1, 1, weight=-1)
+ pytest.raises(nx.NetworkXUnbounded, nx.network_simplex, G)
+
+ G[1][1]["capacity"] = 2
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == -2
+ assert H == {1: {1: 2}}
+
+ G = nx.MultiDiGraph()
+ G.add_edge(1, 1, "x", weight=-1)
+ G.add_edge(1, 1, "y", weight=1)
+ pytest.raises(nx.NetworkXUnbounded, nx.network_simplex, G)
+
+ G[1][1]["x"]["capacity"] = 2
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == -2
+ assert H == {1: {1: {"x": 2, "y": 0}}}
+
+
+def test_bone_shaped():
+ # From #1283
+ G = nx.DiGraph()
+ G.add_node(0, demand=-4)
+ G.add_node(1, demand=2)
+ G.add_node(2, demand=2)
+ G.add_node(3, demand=4)
+ G.add_node(4, demand=-2)
+ G.add_node(5, demand=-2)
+ G.add_edge(0, 1, capacity=4)
+ G.add_edge(0, 2, capacity=4)
+ G.add_edge(4, 3, capacity=4)
+ G.add_edge(5, 3, capacity=4)
+ G.add_edge(0, 3, capacity=0)
+ flowCost, H = nx.network_simplex(G)
+ assert flowCost == 0
+ assert H == {0: {1: 2, 2: 2, 3: 0}, 1: {}, 2: {}, 3: {}, 4: {3: 2}, 5: {3: 2}}
+
+
+def test_graphs_type_exceptions():
+ G = nx.Graph()
+ pytest.raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
+ G = nx.MultiGraph()
+ pytest.raises(nx.NetworkXNotImplemented, nx.network_simplex, G)
+ G = nx.DiGraph()
+ pytest.raises(nx.NetworkXError, nx.network_simplex, G)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/wlm3.gpickle.bz2 b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/wlm3.gpickle.bz2
new file mode 100644
index 00000000..8ce935a8
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/tests/wlm3.gpickle.bz2
Binary files differ
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/utils.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/utils.py
new file mode 100644
index 00000000..03f1d10f
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/flow/utils.py
@@ -0,0 +1,189 @@
+"""
+Utility classes and functions for network flow algorithms.
+"""
+
+from collections import deque
+
+import networkx as nx
+
+__all__ = [
+ "CurrentEdge",
+ "Level",
+ "GlobalRelabelThreshold",
+ "build_residual_network",
+ "detect_unboundedness",
+ "build_flow_dict",
+]
+
+
+class CurrentEdge:
+ """Mechanism for iterating over out-edges incident to a node in a circular
+ manner. StopIteration exception is raised when wraparound occurs.
+ """
+
+ __slots__ = ("_edges", "_it", "_curr")
+
+ def __init__(self, edges):
+ self._edges = edges
+ if self._edges:
+ self._rewind()
+
+ def get(self):
+ return self._curr
+
+ def move_to_next(self):
+ try:
+ self._curr = next(self._it)
+ except StopIteration:
+ self._rewind()
+ raise
+
+ def _rewind(self):
+ self._it = iter(self._edges.items())
+ self._curr = next(self._it)
+
+
+class Level:
+ """Active and inactive nodes in a level."""
+
+ __slots__ = ("active", "inactive")
+
+ def __init__(self):
+ self.active = set()
+ self.inactive = set()
+
+
+class GlobalRelabelThreshold:
+ """Measurement of work before the global relabeling heuristic should be
+ applied.
+ """
+
+ def __init__(self, n, m, freq):
+ self._threshold = (n + m) / freq if freq else float("inf")
+ self._work = 0
+
+ def add_work(self, work):
+ self._work += work
+
+ def is_reached(self):
+ return self._work >= self._threshold
+
+ def clear_work(self):
+ self._work = 0
+
+
+@nx._dispatchable(edge_attrs={"capacity": float("inf")}, returns_graph=True)
+def build_residual_network(G, capacity):
+ """Build a residual network and initialize a zero flow.
+
+ 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.
+
+ """
+ if G.is_multigraph():
+ raise nx.NetworkXError("MultiGraph and MultiDiGraph not supported (yet).")
+
+ R = nx.DiGraph()
+ R.__networkx_cache__ = None # Disable caching
+ R.add_nodes_from(G)
+
+ inf = float("inf")
+ # Extract edges with positive capacities. Self loops excluded.
+ edge_list = [
+ (u, v, attr)
+ for u, v, attr in G.edges(data=True)
+ if u != v and attr.get(capacity, inf) > 0
+ ]
+ # Simulate infinity with three times the sum of the finite edge capacities
+ # or any positive value if the sum is zero. This allows the
+ # infinite-capacity edges to be distinguished for unboundedness detection
+ # and directly participate in residual capacity calculation. If the maximum
+ # flow is finite, these edges cannot appear in the minimum cut and thus
+ # guarantee correctness. Since the residual capacity of an
+ # infinite-capacity edge is always at least 2/3 of inf, while that of an
+ # finite-capacity edge is at most 1/3 of inf, if an operation moves more
+ # than 1/3 of inf units of flow to t, there must be an infinite-capacity
+ # s-t path in G.
+ inf = (
+ 3
+ * sum(
+ attr[capacity]
+ for u, v, attr in edge_list
+ if capacity in attr and attr[capacity] != inf
+ )
+ or 1
+ )
+ if G.is_directed():
+ for u, v, attr in edge_list:
+ r = min(attr.get(capacity, inf), inf)
+ if not R.has_edge(u, v):
+ # Both (u, v) and (v, u) must be present in the residual
+ # network.
+ R.add_edge(u, v, capacity=r)
+ R.add_edge(v, u, capacity=0)
+ else:
+ # The edge (u, v) was added when (v, u) was visited.
+ R[u][v]["capacity"] = r
+ else:
+ for u, v, attr in edge_list:
+ # Add a pair of edges with equal residual capacities.
+ r = min(attr.get(capacity, inf), inf)
+ R.add_edge(u, v, capacity=r)
+ R.add_edge(v, u, capacity=r)
+
+ # Record the value simulating infinity.
+ R.graph["inf"] = inf
+
+ return R
+
+
+@nx._dispatchable(
+ graphs="R",
+ preserve_edge_attrs={"R": {"capacity": float("inf")}},
+ preserve_graph_attrs=True,
+)
+def detect_unboundedness(R, s, t):
+ """Detect an infinite-capacity s-t path in R."""
+ q = deque([s])
+ seen = {s}
+ inf = R.graph["inf"]
+ while q:
+ u = q.popleft()
+ for v, attr in R[u].items():
+ if attr["capacity"] == inf and v not in seen:
+ if v == t:
+ raise nx.NetworkXUnbounded(
+ "Infinite capacity path, flow unbounded above."
+ )
+ seen.add(v)
+ q.append(v)
+
+
+@nx._dispatchable(graphs={"G": 0, "R": 1}, preserve_edge_attrs={"R": {"flow": None}})
+def build_flow_dict(G, R):
+ """Build a flow dictionary from a residual network."""
+ flow_dict = {}
+ for u in G:
+ flow_dict[u] = {v: 0 for v in G[u]}
+ flow_dict[u].update(
+ (v, attr["flow"]) for v, attr in R[u].items() if attr["flow"] > 0
+ )
+ return flow_dict