Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/flow/utils.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Utility classes and functions for network flow algorithms. | |
3 """ | |
4 | |
5 from collections import deque | |
6 import networkx as nx | |
7 | |
8 __all__ = [ | |
9 "CurrentEdge", | |
10 "Level", | |
11 "GlobalRelabelThreshold", | |
12 "build_residual_network", | |
13 "detect_unboundedness", | |
14 "build_flow_dict", | |
15 ] | |
16 | |
17 | |
18 class CurrentEdge: | |
19 """Mechanism for iterating over out-edges incident to a node in a circular | |
20 manner. StopIteration exception is raised when wraparound occurs. | |
21 """ | |
22 | |
23 __slots__ = ("_edges", "_it", "_curr") | |
24 | |
25 def __init__(self, edges): | |
26 self._edges = edges | |
27 if self._edges: | |
28 self._rewind() | |
29 | |
30 def get(self): | |
31 return self._curr | |
32 | |
33 def move_to_next(self): | |
34 try: | |
35 self._curr = next(self._it) | |
36 except StopIteration: | |
37 self._rewind() | |
38 raise | |
39 | |
40 def _rewind(self): | |
41 self._it = iter(self._edges.items()) | |
42 self._curr = next(self._it) | |
43 | |
44 | |
45 class Level: | |
46 """Active and inactive nodes in a level. | |
47 """ | |
48 | |
49 __slots__ = ("active", "inactive") | |
50 | |
51 def __init__(self): | |
52 self.active = set() | |
53 self.inactive = set() | |
54 | |
55 | |
56 class GlobalRelabelThreshold: | |
57 """Measurement of work before the global relabeling heuristic should be | |
58 applied. | |
59 """ | |
60 | |
61 def __init__(self, n, m, freq): | |
62 self._threshold = (n + m) / freq if freq else float("inf") | |
63 self._work = 0 | |
64 | |
65 def add_work(self, work): | |
66 self._work += work | |
67 | |
68 def is_reached(self): | |
69 return self._work >= self._threshold | |
70 | |
71 def clear_work(self): | |
72 self._work = 0 | |
73 | |
74 | |
75 def build_residual_network(G, capacity): | |
76 """Build a residual network and initialize a zero flow. | |
77 | |
78 The residual network :samp:`R` from an input graph :samp:`G` has the | |
79 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair | |
80 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a | |
81 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists | |
82 in :samp:`G`. | |
83 | |
84 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']` | |
85 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists | |
86 in :samp:`G` or zero otherwise. If the capacity is infinite, | |
87 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value | |
88 that does not affect the solution of the problem. This value is stored in | |
89 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`, | |
90 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and | |
91 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`. | |
92 | |
93 The flow value, defined as the total flow into :samp:`t`, the sink, is | |
94 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not | |
95 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such | |
96 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum | |
97 :samp:`s`-:samp:`t` cut. | |
98 | |
99 """ | |
100 if G.is_multigraph(): | |
101 raise nx.NetworkXError("MultiGraph and MultiDiGraph not supported (yet).") | |
102 | |
103 R = nx.DiGraph() | |
104 R.add_nodes_from(G) | |
105 | |
106 inf = float("inf") | |
107 # Extract edges with positive capacities. Self loops excluded. | |
108 edge_list = [ | |
109 (u, v, attr) | |
110 for u, v, attr in G.edges(data=True) | |
111 if u != v and attr.get(capacity, inf) > 0 | |
112 ] | |
113 # Simulate infinity with three times the sum of the finite edge capacities | |
114 # or any positive value if the sum is zero. This allows the | |
115 # infinite-capacity edges to be distinguished for unboundedness detection | |
116 # and directly participate in residual capacity calculation. If the maximum | |
117 # flow is finite, these edges cannot appear in the minimum cut and thus | |
118 # guarantee correctness. Since the residual capacity of an | |
119 # infinite-capacity edge is always at least 2/3 of inf, while that of an | |
120 # finite-capacity edge is at most 1/3 of inf, if an operation moves more | |
121 # than 1/3 of inf units of flow to t, there must be an infinite-capacity | |
122 # s-t path in G. | |
123 inf = ( | |
124 3 | |
125 * sum( | |
126 attr[capacity] | |
127 for u, v, attr in edge_list | |
128 if capacity in attr and attr[capacity] != inf | |
129 ) | |
130 or 1 | |
131 ) | |
132 if G.is_directed(): | |
133 for u, v, attr in edge_list: | |
134 r = min(attr.get(capacity, inf), inf) | |
135 if not R.has_edge(u, v): | |
136 # Both (u, v) and (v, u) must be present in the residual | |
137 # network. | |
138 R.add_edge(u, v, capacity=r) | |
139 R.add_edge(v, u, capacity=0) | |
140 else: | |
141 # The edge (u, v) was added when (v, u) was visited. | |
142 R[u][v]["capacity"] = r | |
143 else: | |
144 for u, v, attr in edge_list: | |
145 # Add a pair of edges with equal residual capacities. | |
146 r = min(attr.get(capacity, inf), inf) | |
147 R.add_edge(u, v, capacity=r) | |
148 R.add_edge(v, u, capacity=r) | |
149 | |
150 # Record the value simulating infinity. | |
151 R.graph["inf"] = inf | |
152 | |
153 return R | |
154 | |
155 | |
156 def detect_unboundedness(R, s, t): | |
157 """Detect an infinite-capacity s-t path in R. | |
158 """ | |
159 q = deque([s]) | |
160 seen = {s} | |
161 inf = R.graph["inf"] | |
162 while q: | |
163 u = q.popleft() | |
164 for v, attr in R[u].items(): | |
165 if attr["capacity"] == inf and v not in seen: | |
166 if v == t: | |
167 raise nx.NetworkXUnbounded( | |
168 "Infinite capacity path, flow unbounded above." | |
169 ) | |
170 seen.add(v) | |
171 q.append(v) | |
172 | |
173 | |
174 def build_flow_dict(G, R): | |
175 """Build a flow dictionary from a residual network. | |
176 """ | |
177 flow_dict = {} | |
178 for u in G: | |
179 flow_dict[u] = {v: 0 for v in G[u]} | |
180 flow_dict[u].update( | |
181 (v, attr["flow"]) for v, attr in R[u].items() if attr["flow"] > 0 | |
182 ) | |
183 return flow_dict |