Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/disjoint_paths.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 """Flow based node and edge disjoint paths.""" | |
2 import networkx as nx | |
3 from networkx.exception import NetworkXNoPath | |
4 | |
5 # Define the default maximum flow function to use for the undelying | |
6 # maximum flow computations | |
7 from networkx.algorithms.flow import edmonds_karp | |
8 from networkx.algorithms.flow import preflow_push | |
9 from networkx.algorithms.flow import shortest_augmenting_path | |
10 | |
11 default_flow_func = edmonds_karp | |
12 # Functions to build auxiliary data structures. | |
13 from .utils import build_auxiliary_node_connectivity | |
14 from .utils import build_auxiliary_edge_connectivity | |
15 | |
16 from itertools import filterfalse as _filterfalse | |
17 | |
18 __all__ = ["edge_disjoint_paths", "node_disjoint_paths"] | |
19 | |
20 | |
21 def edge_disjoint_paths( | |
22 G, s, t, flow_func=None, cutoff=None, auxiliary=None, residual=None | |
23 ): | |
24 """Returns the edges disjoint paths between source and target. | |
25 | |
26 Edge disjoint paths are paths that do not share any edge. The | |
27 number of edge disjoint paths between source and target is equal | |
28 to their edge connectivity. | |
29 | |
30 Parameters | |
31 ---------- | |
32 G : NetworkX graph | |
33 | |
34 s : node | |
35 Source node for the flow. | |
36 | |
37 t : node | |
38 Sink node for the flow. | |
39 | |
40 flow_func : function | |
41 A function for computing the maximum flow among a pair of nodes. | |
42 The function has to accept at least three parameters: a Digraph, | |
43 a source node, and a target node. And return a residual network | |
44 that follows NetworkX conventions (see :meth:`maximum_flow` for | |
45 details). If flow_func is None, the default maximum flow function | |
46 (:meth:`edmonds_karp`) is used. The choice of the default function | |
47 may change from version to version and should not be relied on. | |
48 Default value: None. | |
49 | |
50 cutoff : int | |
51 Maximum number of paths to yield. Some of the maximum flow | |
52 algorithms, such as :meth:`edmonds_karp` (the default) and | |
53 :meth:`shortest_augmenting_path` support the cutoff parameter, | |
54 and will terminate when the flow value reaches or exceeds the | |
55 cutoff. Other algorithms will ignore this parameter. | |
56 Default value: None. | |
57 | |
58 auxiliary : NetworkX DiGraph | |
59 Auxiliary digraph to compute flow based edge connectivity. It has | |
60 to have a graph attribute called mapping with a dictionary mapping | |
61 node names in G and in the auxiliary digraph. If provided | |
62 it will be reused instead of recreated. Default value: None. | |
63 | |
64 residual : NetworkX DiGraph | |
65 Residual network to compute maximum flow. If provided it will be | |
66 reused instead of recreated. Default value: None. | |
67 | |
68 Returns | |
69 ------- | |
70 paths : generator | |
71 A generator of edge independent paths. | |
72 | |
73 Raises | |
74 ------ | |
75 NetworkXNoPath | |
76 If there is no path between source and target. | |
77 | |
78 NetworkXError | |
79 If source or target are not in the graph G. | |
80 | |
81 See also | |
82 -------- | |
83 :meth:`node_disjoint_paths` | |
84 :meth:`edge_connectivity` | |
85 :meth:`maximum_flow` | |
86 :meth:`edmonds_karp` | |
87 :meth:`preflow_push` | |
88 :meth:`shortest_augmenting_path` | |
89 | |
90 Examples | |
91 -------- | |
92 We use in this example the platonic icosahedral graph, which has node | |
93 edge connectivity 5, thus there are 5 edge disjoint paths between any | |
94 pair of nodes. | |
95 | |
96 >>> G = nx.icosahedral_graph() | |
97 >>> len(list(nx.edge_disjoint_paths(G, 0, 6))) | |
98 5 | |
99 | |
100 | |
101 If you need to compute edge disjoint paths on several pairs of | |
102 nodes in the same graph, it is recommended that you reuse the | |
103 data structures that NetworkX uses in the computation: the | |
104 auxiliary digraph for edge connectivity, and the residual | |
105 network for the underlying maximum flow computation. | |
106 | |
107 Example of how to compute edge disjoint paths among all pairs of | |
108 nodes of the platonic icosahedral graph reusing the data | |
109 structures. | |
110 | |
111 >>> import itertools | |
112 >>> # You also have to explicitly import the function for | |
113 >>> # building the auxiliary digraph from the connectivity package | |
114 >>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity | |
115 >>> H = build_auxiliary_edge_connectivity(G) | |
116 >>> # And the function for building the residual network from the | |
117 >>> # flow package | |
118 >>> from networkx.algorithms.flow import build_residual_network | |
119 >>> # Note that the auxiliary digraph has an edge attribute named capacity | |
120 >>> R = build_residual_network(H, "capacity") | |
121 >>> result = {n: {} for n in G} | |
122 >>> # Reuse the auxiliary digraph and the residual network by passing them | |
123 >>> # as arguments | |
124 >>> for u, v in itertools.combinations(G, 2): | |
125 ... k = len(list(nx.edge_disjoint_paths(G, u, v, auxiliary=H, residual=R))) | |
126 ... result[u][v] = k | |
127 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2)) | |
128 True | |
129 | |
130 You can also use alternative flow algorithms for computing edge disjoint | |
131 paths. For instance, in dense networks the algorithm | |
132 :meth:`shortest_augmenting_path` will usually perform better than | |
133 the default :meth:`edmonds_karp` which is faster for sparse | |
134 networks with highly skewed degree distributions. Alternative flow | |
135 functions have to be explicitly imported from the flow package. | |
136 | |
137 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
138 >>> len(list(nx.edge_disjoint_paths(G, 0, 6, flow_func=shortest_augmenting_path))) | |
139 5 | |
140 | |
141 Notes | |
142 ----- | |
143 This is a flow based implementation of edge disjoint paths. We compute | |
144 the maximum flow between source and target on an auxiliary directed | |
145 network. The saturated edges in the residual network after running the | |
146 maximum flow algorithm correspond to edge disjoint paths between source | |
147 and target in the original network. This function handles both directed | |
148 and undirected graphs, and can use all flow algorithms from NetworkX flow | |
149 package. | |
150 | |
151 """ | |
152 if s not in G: | |
153 raise nx.NetworkXError(f"node {s} not in graph") | |
154 if t not in G: | |
155 raise nx.NetworkXError(f"node {t} not in graph") | |
156 | |
157 if flow_func is None: | |
158 flow_func = default_flow_func | |
159 | |
160 if auxiliary is None: | |
161 H = build_auxiliary_edge_connectivity(G) | |
162 else: | |
163 H = auxiliary | |
164 | |
165 # Maximum possible edge disjoint paths | |
166 possible = min(H.out_degree(s), H.in_degree(t)) | |
167 if not possible: | |
168 raise NetworkXNoPath | |
169 | |
170 if cutoff is None: | |
171 cutoff = possible | |
172 else: | |
173 cutoff = min(cutoff, possible) | |
174 | |
175 # Compute maximum flow between source and target. Flow functions in | |
176 # NetworkX return a residual network. | |
177 kwargs = dict( | |
178 capacity="capacity", residual=residual, cutoff=cutoff, value_only=True | |
179 ) | |
180 if flow_func is preflow_push: | |
181 del kwargs["cutoff"] | |
182 if flow_func is shortest_augmenting_path: | |
183 kwargs["two_phase"] = True | |
184 R = flow_func(H, s, t, **kwargs) | |
185 | |
186 if R.graph["flow_value"] == 0: | |
187 raise NetworkXNoPath | |
188 | |
189 # Saturated edges in the residual network form the edge disjoint paths | |
190 # between source and target | |
191 cutset = [ | |
192 (u, v) | |
193 for u, v, d in R.edges(data=True) | |
194 if d["capacity"] == d["flow"] and d["flow"] > 0 | |
195 ] | |
196 # This is equivalent of what flow.utils.build_flow_dict returns, but | |
197 # only for the nodes with saturated edges and without reporting 0 flows. | |
198 flow_dict = {n: {} for edge in cutset for n in edge} | |
199 for u, v in cutset: | |
200 flow_dict[u][v] = 1 | |
201 | |
202 # Rebuild the edge disjoint paths from the flow dictionary. | |
203 paths_found = 0 | |
204 for v in list(flow_dict[s]): | |
205 if paths_found >= cutoff: | |
206 # preflow_push does not support cutoff: we have to | |
207 # keep track of the paths founds and stop at cutoff. | |
208 break | |
209 path = [s] | |
210 if v == t: | |
211 path.append(v) | |
212 yield path | |
213 continue | |
214 u = v | |
215 while u != t: | |
216 path.append(u) | |
217 try: | |
218 u, _ = flow_dict[u].popitem() | |
219 except KeyError: | |
220 break | |
221 else: | |
222 path.append(t) | |
223 yield path | |
224 paths_found += 1 | |
225 | |
226 | |
227 def node_disjoint_paths( | |
228 G, s, t, flow_func=None, cutoff=None, auxiliary=None, residual=None | |
229 ): | |
230 r"""Computes node disjoint paths between source and target. | |
231 | |
232 Node disjoint paths are paths that only share their first and last | |
233 nodes. The number of node independent paths between two nodes is | |
234 equal to their local node connectivity. | |
235 | |
236 Parameters | |
237 ---------- | |
238 G : NetworkX graph | |
239 | |
240 s : node | |
241 Source node. | |
242 | |
243 t : node | |
244 Target node. | |
245 | |
246 flow_func : function | |
247 A function for computing the maximum flow among a pair of nodes. | |
248 The function has to accept at least three parameters: a Digraph, | |
249 a source node, and a target node. And return a residual network | |
250 that follows NetworkX conventions (see :meth:`maximum_flow` for | |
251 details). If flow_func is None, the default maximum flow function | |
252 (:meth:`edmonds_karp`) is used. See below for details. The choice | |
253 of the default function may change from version to version and | |
254 should not be relied on. Default value: None. | |
255 | |
256 cutoff : int | |
257 Maximum number of paths to yield. Some of the maximum flow | |
258 algorithms, such as :meth:`edmonds_karp` (the default) and | |
259 :meth:`shortest_augmenting_path` support the cutoff parameter, | |
260 and will terminate when the flow value reaches or exceeds the | |
261 cutoff. Other algorithms will ignore this parameter. | |
262 Default value: None. | |
263 | |
264 auxiliary : NetworkX DiGraph | |
265 Auxiliary digraph to compute flow based node connectivity. It has | |
266 to have a graph attribute called mapping with a dictionary mapping | |
267 node names in G and in the auxiliary digraph. If provided | |
268 it will be reused instead of recreated. Default value: None. | |
269 | |
270 residual : NetworkX DiGraph | |
271 Residual network to compute maximum flow. If provided it will be | |
272 reused instead of recreated. Default value: None. | |
273 | |
274 Returns | |
275 ------- | |
276 paths : generator | |
277 Generator of node disjoint paths. | |
278 | |
279 Raises | |
280 ------ | |
281 NetworkXNoPath | |
282 If there is no path between source and target. | |
283 | |
284 NetworkXError | |
285 If source or target are not in the graph G. | |
286 | |
287 Examples | |
288 -------- | |
289 We use in this example the platonic icosahedral graph, which has node | |
290 node connectivity 5, thus there are 5 node disjoint paths between any | |
291 pair of non neighbor nodes. | |
292 | |
293 >>> G = nx.icosahedral_graph() | |
294 >>> len(list(nx.node_disjoint_paths(G, 0, 6))) | |
295 5 | |
296 | |
297 If you need to compute node disjoint paths between several pairs of | |
298 nodes in the same graph, it is recommended that you reuse the | |
299 data structures that NetworkX uses in the computation: the | |
300 auxiliary digraph for node connectivity and node cuts, and the | |
301 residual network for the underlying maximum flow computation. | |
302 | |
303 Example of how to compute node disjoint paths reusing the data | |
304 structures: | |
305 | |
306 >>> # You also have to explicitly import the function for | |
307 >>> # building the auxiliary digraph from the connectivity package | |
308 >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity | |
309 >>> H = build_auxiliary_node_connectivity(G) | |
310 >>> # And the function for building the residual network from the | |
311 >>> # flow package | |
312 >>> from networkx.algorithms.flow import build_residual_network | |
313 >>> # Note that the auxiliary digraph has an edge attribute named capacity | |
314 >>> R = build_residual_network(H, "capacity") | |
315 >>> # Reuse the auxiliary digraph and the residual network by passing them | |
316 >>> # as arguments | |
317 >>> len(list(nx.node_disjoint_paths(G, 0, 6, auxiliary=H, residual=R))) | |
318 5 | |
319 | |
320 You can also use alternative flow algorithms for computing node disjoint | |
321 paths. For instance, in dense networks the algorithm | |
322 :meth:`shortest_augmenting_path` will usually perform better than | |
323 the default :meth:`edmonds_karp` which is faster for sparse | |
324 networks with highly skewed degree distributions. Alternative flow | |
325 functions have to be explicitly imported from the flow package. | |
326 | |
327 >>> from networkx.algorithms.flow import shortest_augmenting_path | |
328 >>> len(list(nx.node_disjoint_paths(G, 0, 6, flow_func=shortest_augmenting_path))) | |
329 5 | |
330 | |
331 Notes | |
332 ----- | |
333 This is a flow based implementation of node disjoint paths. We compute | |
334 the maximum flow between source and target on an auxiliary directed | |
335 network. The saturated edges in the residual network after running the | |
336 maximum flow algorithm correspond to node disjoint paths between source | |
337 and target in the original network. This function handles both directed | |
338 and undirected graphs, and can use all flow algorithms from NetworkX flow | |
339 package. | |
340 | |
341 See also | |
342 -------- | |
343 :meth:`edge_disjoint_paths` | |
344 :meth:`node_connectivity` | |
345 :meth:`maximum_flow` | |
346 :meth:`edmonds_karp` | |
347 :meth:`preflow_push` | |
348 :meth:`shortest_augmenting_path` | |
349 | |
350 """ | |
351 if s not in G: | |
352 raise nx.NetworkXError(f"node {s} not in graph") | |
353 if t not in G: | |
354 raise nx.NetworkXError(f"node {t} not in graph") | |
355 | |
356 if auxiliary is None: | |
357 H = build_auxiliary_node_connectivity(G) | |
358 else: | |
359 H = auxiliary | |
360 | |
361 mapping = H.graph.get("mapping", None) | |
362 if mapping is None: | |
363 raise nx.NetworkXError("Invalid auxiliary digraph.") | |
364 | |
365 # Maximum possible edge disjoint paths | |
366 possible = min(H.out_degree(f"{mapping[s]}B"), H.in_degree(f"{mapping[t]}A")) | |
367 if not possible: | |
368 raise NetworkXNoPath | |
369 | |
370 if cutoff is None: | |
371 cutoff = possible | |
372 else: | |
373 cutoff = min(cutoff, possible) | |
374 | |
375 kwargs = dict(flow_func=flow_func, residual=residual, auxiliary=H, cutoff=cutoff) | |
376 | |
377 # The edge disjoint paths in the auxiliary digraph correspond to the node | |
378 # disjoint paths in the original graph. | |
379 paths_edges = edge_disjoint_paths(H, f"{mapping[s]}B", f"{mapping[t]}A", **kwargs) | |
380 for path in paths_edges: | |
381 # Each node in the original graph maps to two nodes in auxiliary graph | |
382 yield list(_unique_everseen(H.nodes[node]["id"] for node in path)) | |
383 | |
384 | |
385 def _unique_everseen(iterable): | |
386 # Adapted from https://docs.python.org/3/library/itertools.html examples | |
387 "List unique elements, preserving order. Remember all elements ever seen." | |
388 # unique_everseen('AAAABBBCCDAABBB') --> A B C D | |
389 seen = set() | |
390 seen_add = seen.add | |
391 for element in _filterfalse(seen.__contains__, iterable): | |
392 seen_add(element) | |
393 yield element |