Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/unweighted.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 Shortest path algorithms for unweighted graphs. | |
3 """ | |
4 import networkx as nx | |
5 | |
6 __all__ = [ | |
7 "bidirectional_shortest_path", | |
8 "single_source_shortest_path", | |
9 "single_source_shortest_path_length", | |
10 "single_target_shortest_path", | |
11 "single_target_shortest_path_length", | |
12 "all_pairs_shortest_path", | |
13 "all_pairs_shortest_path_length", | |
14 "predecessor", | |
15 ] | |
16 | |
17 | |
18 def single_source_shortest_path_length(G, source, cutoff=None): | |
19 """Compute the shortest path lengths from source to all reachable nodes. | |
20 | |
21 Parameters | |
22 ---------- | |
23 G : NetworkX graph | |
24 | |
25 source : node | |
26 Starting node for path | |
27 | |
28 cutoff : integer, optional | |
29 Depth to stop the search. Only paths of length <= cutoff are returned. | |
30 | |
31 Returns | |
32 ------- | |
33 lengths : dict | |
34 Dict keyed by node to shortest path length to source. | |
35 | |
36 Examples | |
37 -------- | |
38 >>> G = nx.path_graph(5) | |
39 >>> length = nx.single_source_shortest_path_length(G, 0) | |
40 >>> length[4] | |
41 4 | |
42 >>> for node in length: | |
43 ... print(f"{node}: {length[node]}") | |
44 0: 0 | |
45 1: 1 | |
46 2: 2 | |
47 3: 3 | |
48 4: 4 | |
49 | |
50 See Also | |
51 -------- | |
52 shortest_path_length | |
53 """ | |
54 if source not in G: | |
55 raise nx.NodeNotFound(f"Source {source} is not in G") | |
56 if cutoff is None: | |
57 cutoff = float("inf") | |
58 nextlevel = {source: 1} | |
59 return dict(_single_shortest_path_length(G.adj, nextlevel, cutoff)) | |
60 | |
61 | |
62 def _single_shortest_path_length(adj, firstlevel, cutoff): | |
63 """Yields (node, level) in a breadth first search | |
64 | |
65 Shortest Path Length helper function | |
66 Parameters | |
67 ---------- | |
68 adj : dict | |
69 Adjacency dict or view | |
70 firstlevel : dict | |
71 starting nodes, e.g. {source: 1} or {target: 1} | |
72 cutoff : int or float | |
73 level at which we stop the process | |
74 """ | |
75 seen = {} # level (number of hops) when seen in BFS | |
76 level = 0 # the current level | |
77 nextlevel = set(firstlevel) # set of nodes to check at next level | |
78 n = len(adj) | |
79 while nextlevel and cutoff >= level: | |
80 thislevel = nextlevel # advance to next level | |
81 nextlevel = set() # and start a new set (fringe) | |
82 found = [] | |
83 for v in thislevel: | |
84 if v not in seen: | |
85 seen[v] = level # set the level of vertex v | |
86 found.append(v) | |
87 yield (v, level) | |
88 if len(seen) == n: | |
89 return | |
90 for v in found: | |
91 nextlevel.update(adj[v]) | |
92 level += 1 | |
93 del seen | |
94 | |
95 | |
96 def single_target_shortest_path_length(G, target, cutoff=None): | |
97 """Compute the shortest path lengths to target from all reachable nodes. | |
98 | |
99 Parameters | |
100 ---------- | |
101 G : NetworkX graph | |
102 | |
103 target : node | |
104 Target node for path | |
105 | |
106 cutoff : integer, optional | |
107 Depth to stop the search. Only paths of length <= cutoff are returned. | |
108 | |
109 Returns | |
110 ------- | |
111 lengths : iterator | |
112 (source, shortest path length) iterator | |
113 | |
114 Examples | |
115 -------- | |
116 >>> G = nx.path_graph(5, create_using=nx.DiGraph()) | |
117 >>> length = dict(nx.single_target_shortest_path_length(G, 4)) | |
118 >>> length[0] | |
119 4 | |
120 >>> for node in range(5): | |
121 ... print(f"{node}: {length[node]}") | |
122 0: 4 | |
123 1: 3 | |
124 2: 2 | |
125 3: 1 | |
126 4: 0 | |
127 | |
128 See Also | |
129 -------- | |
130 single_source_shortest_path_length, shortest_path_length | |
131 """ | |
132 if target not in G: | |
133 raise nx.NodeNotFound(f"Target {target} is not in G") | |
134 | |
135 if cutoff is None: | |
136 cutoff = float("inf") | |
137 # handle either directed or undirected | |
138 adj = G.pred if G.is_directed() else G.adj | |
139 nextlevel = {target: 1} | |
140 return _single_shortest_path_length(adj, nextlevel, cutoff) | |
141 | |
142 | |
143 def all_pairs_shortest_path_length(G, cutoff=None): | |
144 """Computes the shortest path lengths between all nodes in `G`. | |
145 | |
146 Parameters | |
147 ---------- | |
148 G : NetworkX graph | |
149 | |
150 cutoff : integer, optional | |
151 Depth at which to stop the search. Only paths of length at most | |
152 `cutoff` are returned. | |
153 | |
154 Returns | |
155 ------- | |
156 lengths : iterator | |
157 (source, dictionary) iterator with dictionary keyed by target and | |
158 shortest path length as the key value. | |
159 | |
160 Notes | |
161 ----- | |
162 The iterator returned only has reachable node pairs. | |
163 | |
164 Examples | |
165 -------- | |
166 >>> G = nx.path_graph(5) | |
167 >>> length = dict(nx.all_pairs_shortest_path_length(G)) | |
168 >>> for node in [0, 1, 2, 3, 4]: | |
169 ... print(f"1 - {node}: {length[1][node]}") | |
170 1 - 0: 1 | |
171 1 - 1: 0 | |
172 1 - 2: 1 | |
173 1 - 3: 2 | |
174 1 - 4: 3 | |
175 >>> length[3][2] | |
176 1 | |
177 >>> length[2][2] | |
178 0 | |
179 | |
180 """ | |
181 length = single_source_shortest_path_length | |
182 # TODO This can be trivially parallelized. | |
183 for n in G: | |
184 yield (n, length(G, n, cutoff=cutoff)) | |
185 | |
186 | |
187 def bidirectional_shortest_path(G, source, target): | |
188 """Returns a list of nodes in a shortest path between source and target. | |
189 | |
190 Parameters | |
191 ---------- | |
192 G : NetworkX graph | |
193 | |
194 source : node label | |
195 starting node for path | |
196 | |
197 target : node label | |
198 ending node for path | |
199 | |
200 Returns | |
201 ------- | |
202 path: list | |
203 List of nodes in a path from source to target. | |
204 | |
205 Raises | |
206 ------ | |
207 NetworkXNoPath | |
208 If no path exists between source and target. | |
209 | |
210 See Also | |
211 -------- | |
212 shortest_path | |
213 | |
214 Notes | |
215 ----- | |
216 This algorithm is used by shortest_path(G, source, target). | |
217 """ | |
218 | |
219 if source not in G or target not in G: | |
220 msg = f"Either source {source} or target {target} is not in G" | |
221 raise nx.NodeNotFound(msg) | |
222 | |
223 # call helper to do the real work | |
224 results = _bidirectional_pred_succ(G, source, target) | |
225 pred, succ, w = results | |
226 | |
227 # build path from pred+w+succ | |
228 path = [] | |
229 # from source to w | |
230 while w is not None: | |
231 path.append(w) | |
232 w = pred[w] | |
233 path.reverse() | |
234 # from w to target | |
235 w = succ[path[-1]] | |
236 while w is not None: | |
237 path.append(w) | |
238 w = succ[w] | |
239 | |
240 return path | |
241 | |
242 | |
243 def _bidirectional_pred_succ(G, source, target): | |
244 """Bidirectional shortest path helper. | |
245 | |
246 Returns (pred, succ, w) where | |
247 pred is a dictionary of predecessors from w to the source, and | |
248 succ is a dictionary of successors from w to the target. | |
249 """ | |
250 # does BFS from both source and target and meets in the middle | |
251 if target == source: | |
252 return ({target: None}, {source: None}, source) | |
253 | |
254 # handle either directed or undirected | |
255 if G.is_directed(): | |
256 Gpred = G.pred | |
257 Gsucc = G.succ | |
258 else: | |
259 Gpred = G.adj | |
260 Gsucc = G.adj | |
261 | |
262 # predecesssor and successors in search | |
263 pred = {source: None} | |
264 succ = {target: None} | |
265 | |
266 # initialize fringes, start with forward | |
267 forward_fringe = [source] | |
268 reverse_fringe = [target] | |
269 | |
270 while forward_fringe and reverse_fringe: | |
271 if len(forward_fringe) <= len(reverse_fringe): | |
272 this_level = forward_fringe | |
273 forward_fringe = [] | |
274 for v in this_level: | |
275 for w in Gsucc[v]: | |
276 if w not in pred: | |
277 forward_fringe.append(w) | |
278 pred[w] = v | |
279 if w in succ: # path found | |
280 return pred, succ, w | |
281 else: | |
282 this_level = reverse_fringe | |
283 reverse_fringe = [] | |
284 for v in this_level: | |
285 for w in Gpred[v]: | |
286 if w not in succ: | |
287 succ[w] = v | |
288 reverse_fringe.append(w) | |
289 if w in pred: # found path | |
290 return pred, succ, w | |
291 | |
292 raise nx.NetworkXNoPath(f"No path between {source} and {target}.") | |
293 | |
294 | |
295 def single_source_shortest_path(G, source, cutoff=None): | |
296 """Compute shortest path between source | |
297 and all other nodes reachable from source. | |
298 | |
299 Parameters | |
300 ---------- | |
301 G : NetworkX graph | |
302 | |
303 source : node label | |
304 Starting node for path | |
305 | |
306 cutoff : integer, optional | |
307 Depth to stop the search. Only paths of length <= cutoff are returned. | |
308 | |
309 Returns | |
310 ------- | |
311 lengths : dictionary | |
312 Dictionary, keyed by target, of shortest paths. | |
313 | |
314 Examples | |
315 -------- | |
316 >>> G = nx.path_graph(5) | |
317 >>> path = nx.single_source_shortest_path(G, 0) | |
318 >>> path[4] | |
319 [0, 1, 2, 3, 4] | |
320 | |
321 Notes | |
322 ----- | |
323 The shortest path is not necessarily unique. So there can be multiple | |
324 paths between the source and each target node, all of which have the | |
325 same 'shortest' length. For each target node, this function returns | |
326 only one of those paths. | |
327 | |
328 See Also | |
329 -------- | |
330 shortest_path | |
331 """ | |
332 if source not in G: | |
333 raise nx.NodeNotFound(f"Source {source} not in G") | |
334 | |
335 def join(p1, p2): | |
336 return p1 + p2 | |
337 | |
338 if cutoff is None: | |
339 cutoff = float("inf") | |
340 nextlevel = {source: 1} # list of nodes to check at next level | |
341 paths = {source: [source]} # paths dictionary (paths to key from source) | |
342 return dict(_single_shortest_path(G.adj, nextlevel, paths, cutoff, join)) | |
343 | |
344 | |
345 def _single_shortest_path(adj, firstlevel, paths, cutoff, join): | |
346 """Returns shortest paths | |
347 | |
348 Shortest Path helper function | |
349 Parameters | |
350 ---------- | |
351 adj : dict | |
352 Adjacency dict or view | |
353 firstlevel : dict | |
354 starting nodes, e.g. {source: 1} or {target: 1} | |
355 paths : dict | |
356 paths for starting nodes, e.g. {source: [source]} | |
357 cutoff : int or float | |
358 level at which we stop the process | |
359 join : function | |
360 function to construct a path from two partial paths. Requires two | |
361 list inputs `p1` and `p2`, and returns a list. Usually returns | |
362 `p1 + p2` (forward from source) or `p2 + p1` (backward from target) | |
363 """ | |
364 level = 0 # the current level | |
365 nextlevel = firstlevel | |
366 while nextlevel and cutoff > level: | |
367 thislevel = nextlevel | |
368 nextlevel = {} | |
369 for v in thislevel: | |
370 for w in adj[v]: | |
371 if w not in paths: | |
372 paths[w] = join(paths[v], [w]) | |
373 nextlevel[w] = 1 | |
374 level += 1 | |
375 return paths | |
376 | |
377 | |
378 def single_target_shortest_path(G, target, cutoff=None): | |
379 """Compute shortest path to target from all nodes that reach target. | |
380 | |
381 Parameters | |
382 ---------- | |
383 G : NetworkX graph | |
384 | |
385 target : node label | |
386 Target node for path | |
387 | |
388 cutoff : integer, optional | |
389 Depth to stop the search. Only paths of length <= cutoff are returned. | |
390 | |
391 Returns | |
392 ------- | |
393 lengths : dictionary | |
394 Dictionary, keyed by target, of shortest paths. | |
395 | |
396 Examples | |
397 -------- | |
398 >>> G = nx.path_graph(5, create_using=nx.DiGraph()) | |
399 >>> path = nx.single_target_shortest_path(G, 4) | |
400 >>> path[0] | |
401 [0, 1, 2, 3, 4] | |
402 | |
403 Notes | |
404 ----- | |
405 The shortest path is not necessarily unique. So there can be multiple | |
406 paths between the source and each target node, all of which have the | |
407 same 'shortest' length. For each target node, this function returns | |
408 only one of those paths. | |
409 | |
410 See Also | |
411 -------- | |
412 shortest_path, single_source_shortest_path | |
413 """ | |
414 if target not in G: | |
415 raise nx.NodeNotFound(f"Target {target} not in G") | |
416 | |
417 def join(p1, p2): | |
418 return p2 + p1 | |
419 | |
420 # handle undirected graphs | |
421 adj = G.pred if G.is_directed() else G.adj | |
422 if cutoff is None: | |
423 cutoff = float("inf") | |
424 nextlevel = {target: 1} # list of nodes to check at next level | |
425 paths = {target: [target]} # paths dictionary (paths to key from source) | |
426 return dict(_single_shortest_path(adj, nextlevel, paths, cutoff, join)) | |
427 | |
428 | |
429 def all_pairs_shortest_path(G, cutoff=None): | |
430 """Compute shortest paths between all nodes. | |
431 | |
432 Parameters | |
433 ---------- | |
434 G : NetworkX graph | |
435 | |
436 cutoff : integer, optional | |
437 Depth at which to stop the search. Only paths of length at most | |
438 `cutoff` are returned. | |
439 | |
440 Returns | |
441 ------- | |
442 lengths : dictionary | |
443 Dictionary, keyed by source and target, of shortest paths. | |
444 | |
445 Examples | |
446 -------- | |
447 >>> G = nx.path_graph(5) | |
448 >>> path = dict(nx.all_pairs_shortest_path(G)) | |
449 >>> print(path[0][4]) | |
450 [0, 1, 2, 3, 4] | |
451 | |
452 See Also | |
453 -------- | |
454 floyd_warshall() | |
455 | |
456 """ | |
457 # TODO This can be trivially parallelized. | |
458 for n in G: | |
459 yield (n, single_source_shortest_path(G, n, cutoff=cutoff)) | |
460 | |
461 | |
462 def predecessor(G, source, target=None, cutoff=None, return_seen=None): | |
463 """Returns dict of predecessors for the path from source to all nodes in G | |
464 | |
465 | |
466 Parameters | |
467 ---------- | |
468 G : NetworkX graph | |
469 | |
470 source : node label | |
471 Starting node for path | |
472 | |
473 target : node label, optional | |
474 Ending node for path. If provided only predecessors between | |
475 source and target are returned | |
476 | |
477 cutoff : integer, optional | |
478 Depth to stop the search. Only paths of length <= cutoff are returned. | |
479 | |
480 | |
481 Returns | |
482 ------- | |
483 pred : dictionary | |
484 Dictionary, keyed by node, of predecessors in the shortest path. | |
485 | |
486 Examples | |
487 -------- | |
488 >>> G = nx.path_graph(4) | |
489 >>> list(G) | |
490 [0, 1, 2, 3] | |
491 >>> nx.predecessor(G, 0) | |
492 {0: [], 1: [0], 2: [1], 3: [2]} | |
493 | |
494 """ | |
495 if source not in G: | |
496 raise nx.NodeNotFound(f"Source {source} not in G") | |
497 | |
498 level = 0 # the current level | |
499 nextlevel = [source] # list of nodes to check at next level | |
500 seen = {source: level} # level (number of hops) when seen in BFS | |
501 pred = {source: []} # predecessor dictionary | |
502 while nextlevel: | |
503 level = level + 1 | |
504 thislevel = nextlevel | |
505 nextlevel = [] | |
506 for v in thislevel: | |
507 for w in G[v]: | |
508 if w not in seen: | |
509 pred[w] = [v] | |
510 seen[w] = level | |
511 nextlevel.append(w) | |
512 elif seen[w] == level: # add v to predecessor list if it | |
513 pred[w].append(v) # is at the correct level | |
514 if cutoff and cutoff <= level: | |
515 break | |
516 | |
517 if target is not None: | |
518 if return_seen: | |
519 if target not in pred: | |
520 return ([], -1) # No predecessor | |
521 return (pred[target], seen[target]) | |
522 else: | |
523 if target not in pred: | |
524 return [] # No predecessor | |
525 return pred[target] | |
526 else: | |
527 if return_seen: | |
528 return (pred, seen) | |
529 else: | |
530 return pred |