1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
"""
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
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.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
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)
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
|
