Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/connectivity.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 """ Fast approximation for node connectivity | |
2 """ | |
3 import itertools | |
4 from operator import itemgetter | |
5 | |
6 import networkx as nx | |
7 | |
8 __all__ = [ | |
9 "local_node_connectivity", | |
10 "node_connectivity", | |
11 "all_pairs_node_connectivity", | |
12 ] | |
13 | |
14 INF = float("inf") | |
15 | |
16 | |
17 def local_node_connectivity(G, source, target, cutoff=None): | |
18 """Compute node connectivity between source and target. | |
19 | |
20 Pairwise or local node connectivity between two distinct and nonadjacent | |
21 nodes is the minimum number of nodes that must be removed (minimum | |
22 separating cutset) to disconnect them. By Menger's theorem, this is equal | |
23 to the number of node independent paths (paths that share no nodes other | |
24 than source and target). Which is what we compute in this function. | |
25 | |
26 This algorithm is a fast approximation that gives an strict lower | |
27 bound on the actual number of node independent paths between two nodes [1]_. | |
28 It works for both directed and undirected graphs. | |
29 | |
30 Parameters | |
31 ---------- | |
32 | |
33 G : NetworkX graph | |
34 | |
35 source : node | |
36 Starting node for node connectivity | |
37 | |
38 target : node | |
39 Ending node for node connectivity | |
40 | |
41 cutoff : integer | |
42 Maximum node connectivity to consider. If None, the minimum degree | |
43 of source or target is used as a cutoff. Default value None. | |
44 | |
45 Returns | |
46 ------- | |
47 k: integer | |
48 pairwise node connectivity | |
49 | |
50 Examples | |
51 -------- | |
52 >>> # Platonic octahedral graph has node connectivity 4 | |
53 >>> # for each non adjacent node pair | |
54 >>> from networkx.algorithms import approximation as approx | |
55 >>> G = nx.octahedral_graph() | |
56 >>> approx.local_node_connectivity(G, 0, 5) | |
57 4 | |
58 | |
59 Notes | |
60 ----- | |
61 This algorithm [1]_ finds node independents paths between two nodes by | |
62 computing their shortest path using BFS, marking the nodes of the path | |
63 found as 'used' and then searching other shortest paths excluding the | |
64 nodes marked as used until no more paths exist. It is not exact because | |
65 a shortest path could use nodes that, if the path were longer, may belong | |
66 to two different node independent paths. Thus it only guarantees an | |
67 strict lower bound on node connectivity. | |
68 | |
69 Note that the authors propose a further refinement, losing accuracy and | |
70 gaining speed, which is not implemented yet. | |
71 | |
72 See also | |
73 -------- | |
74 all_pairs_node_connectivity | |
75 node_connectivity | |
76 | |
77 References | |
78 ---------- | |
79 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for | |
80 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 | |
81 http://eclectic.ss.uci.edu/~drwhite/working.pdf | |
82 | |
83 """ | |
84 if target == source: | |
85 raise nx.NetworkXError("source and target have to be different nodes.") | |
86 | |
87 # Maximum possible node independent paths | |
88 if G.is_directed(): | |
89 possible = min(G.out_degree(source), G.in_degree(target)) | |
90 else: | |
91 possible = min(G.degree(source), G.degree(target)) | |
92 | |
93 K = 0 | |
94 if not possible: | |
95 return K | |
96 | |
97 if cutoff is None: | |
98 cutoff = INF | |
99 | |
100 exclude = set() | |
101 for i in range(min(possible, cutoff)): | |
102 try: | |
103 path = _bidirectional_shortest_path(G, source, target, exclude) | |
104 exclude.update(set(path)) | |
105 K += 1 | |
106 except nx.NetworkXNoPath: | |
107 break | |
108 | |
109 return K | |
110 | |
111 | |
112 def node_connectivity(G, s=None, t=None): | |
113 r"""Returns an approximation for node connectivity for a graph or digraph G. | |
114 | |
115 Node connectivity is equal to the minimum number of nodes that | |
116 must be removed to disconnect G or render it trivial. By Menger's theorem, | |
117 this is equal to the number of node independent paths (paths that | |
118 share no nodes other than source and target). | |
119 | |
120 If source and target nodes are provided, this function returns the | |
121 local node connectivity: the minimum number of nodes that must be | |
122 removed to break all paths from source to target in G. | |
123 | |
124 This algorithm is based on a fast approximation that gives an strict lower | |
125 bound on the actual number of node independent paths between two nodes [1]_. | |
126 It works for both directed and undirected graphs. | |
127 | |
128 Parameters | |
129 ---------- | |
130 G : NetworkX graph | |
131 Undirected graph | |
132 | |
133 s : node | |
134 Source node. Optional. Default value: None. | |
135 | |
136 t : node | |
137 Target node. Optional. Default value: None. | |
138 | |
139 Returns | |
140 ------- | |
141 K : integer | |
142 Node connectivity of G, or local node connectivity if source | |
143 and target are provided. | |
144 | |
145 Examples | |
146 -------- | |
147 >>> # Platonic octahedral graph is 4-node-connected | |
148 >>> from networkx.algorithms import approximation as approx | |
149 >>> G = nx.octahedral_graph() | |
150 >>> approx.node_connectivity(G) | |
151 4 | |
152 | |
153 Notes | |
154 ----- | |
155 This algorithm [1]_ finds node independents paths between two nodes by | |
156 computing their shortest path using BFS, marking the nodes of the path | |
157 found as 'used' and then searching other shortest paths excluding the | |
158 nodes marked as used until no more paths exist. It is not exact because | |
159 a shortest path could use nodes that, if the path were longer, may belong | |
160 to two different node independent paths. Thus it only guarantees an | |
161 strict lower bound on node connectivity. | |
162 | |
163 See also | |
164 -------- | |
165 all_pairs_node_connectivity | |
166 local_node_connectivity | |
167 | |
168 References | |
169 ---------- | |
170 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for | |
171 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 | |
172 http://eclectic.ss.uci.edu/~drwhite/working.pdf | |
173 | |
174 """ | |
175 if (s is not None and t is None) or (s is None and t is not None): | |
176 raise nx.NetworkXError("Both source and target must be specified.") | |
177 | |
178 # Local node connectivity | |
179 if s is not None and t is not None: | |
180 if s not in G: | |
181 raise nx.NetworkXError(f"node {s} not in graph") | |
182 if t not in G: | |
183 raise nx.NetworkXError(f"node {t} not in graph") | |
184 return local_node_connectivity(G, s, t) | |
185 | |
186 # Global node connectivity | |
187 if G.is_directed(): | |
188 connected_func = nx.is_weakly_connected | |
189 iter_func = itertools.permutations | |
190 | |
191 def neighbors(v): | |
192 return itertools.chain(G.predecessors(v), G.successors(v)) | |
193 | |
194 else: | |
195 connected_func = nx.is_connected | |
196 iter_func = itertools.combinations | |
197 neighbors = G.neighbors | |
198 | |
199 if not connected_func(G): | |
200 return 0 | |
201 | |
202 # Choose a node with minimum degree | |
203 v, minimum_degree = min(G.degree(), key=itemgetter(1)) | |
204 # Node connectivity is bounded by minimum degree | |
205 K = minimum_degree | |
206 # compute local node connectivity with all non-neighbors nodes | |
207 # and store the minimum | |
208 for w in set(G) - set(neighbors(v)) - {v}: | |
209 K = min(K, local_node_connectivity(G, v, w, cutoff=K)) | |
210 # Same for non adjacent pairs of neighbors of v | |
211 for x, y in iter_func(neighbors(v), 2): | |
212 if y not in G[x] and x != y: | |
213 K = min(K, local_node_connectivity(G, x, y, cutoff=K)) | |
214 return K | |
215 | |
216 | |
217 def all_pairs_node_connectivity(G, nbunch=None, cutoff=None): | |
218 """ Compute node connectivity between all pairs of nodes. | |
219 | |
220 Pairwise or local node connectivity between two distinct and nonadjacent | |
221 nodes is the minimum number of nodes that must be removed (minimum | |
222 separating cutset) to disconnect them. By Menger's theorem, this is equal | |
223 to the number of node independent paths (paths that share no nodes other | |
224 than source and target). Which is what we compute in this function. | |
225 | |
226 This algorithm is a fast approximation that gives an strict lower | |
227 bound on the actual number of node independent paths between two nodes [1]_. | |
228 It works for both directed and undirected graphs. | |
229 | |
230 | |
231 Parameters | |
232 ---------- | |
233 G : NetworkX graph | |
234 | |
235 nbunch: container | |
236 Container of nodes. If provided node connectivity will be computed | |
237 only over pairs of nodes in nbunch. | |
238 | |
239 cutoff : integer | |
240 Maximum node connectivity to consider. If None, the minimum degree | |
241 of source or target is used as a cutoff in each pair of nodes. | |
242 Default value None. | |
243 | |
244 Returns | |
245 ------- | |
246 K : dictionary | |
247 Dictionary, keyed by source and target, of pairwise node connectivity | |
248 | |
249 See Also | |
250 -------- | |
251 local_node_connectivity | |
252 node_connectivity | |
253 | |
254 References | |
255 ---------- | |
256 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for | |
257 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 | |
258 http://eclectic.ss.uci.edu/~drwhite/working.pdf | |
259 """ | |
260 if nbunch is None: | |
261 nbunch = G | |
262 else: | |
263 nbunch = set(nbunch) | |
264 | |
265 directed = G.is_directed() | |
266 if directed: | |
267 iter_func = itertools.permutations | |
268 else: | |
269 iter_func = itertools.combinations | |
270 | |
271 all_pairs = {n: {} for n in nbunch} | |
272 | |
273 for u, v in iter_func(nbunch, 2): | |
274 k = local_node_connectivity(G, u, v, cutoff=cutoff) | |
275 all_pairs[u][v] = k | |
276 if not directed: | |
277 all_pairs[v][u] = k | |
278 | |
279 return all_pairs | |
280 | |
281 | |
282 def _bidirectional_shortest_path(G, source, target, exclude): | |
283 """Returns shortest path between source and target ignoring nodes in the | |
284 container 'exclude'. | |
285 | |
286 Parameters | |
287 ---------- | |
288 | |
289 G : NetworkX graph | |
290 | |
291 source : node | |
292 Starting node for path | |
293 | |
294 target : node | |
295 Ending node for path | |
296 | |
297 exclude: container | |
298 Container for nodes to exclude from the search for shortest paths | |
299 | |
300 Returns | |
301 ------- | |
302 path: list | |
303 Shortest path between source and target ignoring nodes in 'exclude' | |
304 | |
305 Raises | |
306 ------ | |
307 NetworkXNoPath | |
308 If there is no path or if nodes are adjacent and have only one path | |
309 between them | |
310 | |
311 Notes | |
312 ----- | |
313 This function and its helper are originally from | |
314 networkx.algorithms.shortest_paths.unweighted and are modified to | |
315 accept the extra parameter 'exclude', which is a container for nodes | |
316 already used in other paths that should be ignored. | |
317 | |
318 References | |
319 ---------- | |
320 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for | |
321 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035 | |
322 http://eclectic.ss.uci.edu/~drwhite/working.pdf | |
323 | |
324 """ | |
325 # call helper to do the real work | |
326 results = _bidirectional_pred_succ(G, source, target, exclude) | |
327 pred, succ, w = results | |
328 | |
329 # build path from pred+w+succ | |
330 path = [] | |
331 # from source to w | |
332 while w is not None: | |
333 path.append(w) | |
334 w = pred[w] | |
335 path.reverse() | |
336 # from w to target | |
337 w = succ[path[-1]] | |
338 while w is not None: | |
339 path.append(w) | |
340 w = succ[w] | |
341 | |
342 return path | |
343 | |
344 | |
345 def _bidirectional_pred_succ(G, source, target, exclude): | |
346 # does BFS from both source and target and meets in the middle | |
347 # excludes nodes in the container "exclude" from the search | |
348 if source is None or target is None: | |
349 raise nx.NetworkXException( | |
350 "Bidirectional shortest path called without source or target" | |
351 ) | |
352 if target == source: | |
353 return ({target: None}, {source: None}, source) | |
354 | |
355 # handle either directed or undirected | |
356 if G.is_directed(): | |
357 Gpred = G.predecessors | |
358 Gsucc = G.successors | |
359 else: | |
360 Gpred = G.neighbors | |
361 Gsucc = G.neighbors | |
362 | |
363 # predecesssor and successors in search | |
364 pred = {source: None} | |
365 succ = {target: None} | |
366 | |
367 # initialize fringes, start with forward | |
368 forward_fringe = [source] | |
369 reverse_fringe = [target] | |
370 | |
371 level = 0 | |
372 | |
373 while forward_fringe and reverse_fringe: | |
374 # Make sure that we iterate one step forward and one step backwards | |
375 # thus source and target will only trigger "found path" when they are | |
376 # adjacent and then they can be safely included in the container 'exclude' | |
377 level += 1 | |
378 if not level % 2 == 0: | |
379 this_level = forward_fringe | |
380 forward_fringe = [] | |
381 for v in this_level: | |
382 for w in Gsucc(v): | |
383 if w in exclude: | |
384 continue | |
385 if w not in pred: | |
386 forward_fringe.append(w) | |
387 pred[w] = v | |
388 if w in succ: | |
389 return pred, succ, w # found path | |
390 else: | |
391 this_level = reverse_fringe | |
392 reverse_fringe = [] | |
393 for v in this_level: | |
394 for w in Gpred(v): | |
395 if w in exclude: | |
396 continue | |
397 if w not in succ: | |
398 succ[w] = v | |
399 reverse_fringe.append(w) | |
400 if w in pred: | |
401 return pred, succ, w # found path | |
402 | |
403 raise nx.NetworkXNoPath(f"No path between {source} and {target}.") |