Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/shortest_paths/unweighted.py: 13%
169 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Shortest path algorithms for unweighted graphs.
3"""
4import warnings
6import networkx as nx
8__all__ = [
9 "bidirectional_shortest_path",
10 "single_source_shortest_path",
11 "single_source_shortest_path_length",
12 "single_target_shortest_path",
13 "single_target_shortest_path_length",
14 "all_pairs_shortest_path",
15 "all_pairs_shortest_path_length",
16 "predecessor",
17]
20@nx._dispatch
21def single_source_shortest_path_length(G, source, cutoff=None):
22 """Compute the shortest path lengths from source to all reachable nodes.
24 Parameters
25 ----------
26 G : NetworkX graph
28 source : node
29 Starting node for path
31 cutoff : integer, optional
32 Depth to stop the search. Only paths of length <= cutoff are returned.
34 Returns
35 -------
36 lengths : dict
37 Dict keyed by node to shortest path length to source.
39 Examples
40 --------
41 >>> G = nx.path_graph(5)
42 >>> length = nx.single_source_shortest_path_length(G, 0)
43 >>> length[4]
44 4
45 >>> for node in length:
46 ... print(f"{node}: {length[node]}")
47 0: 0
48 1: 1
49 2: 2
50 3: 3
51 4: 4
53 See Also
54 --------
55 shortest_path_length
56 """
57 if source not in G:
58 raise nx.NodeNotFound(f"Source {source} is not in G")
59 if cutoff is None:
60 cutoff = float("inf")
61 nextlevel = [source]
62 return dict(_single_shortest_path_length(G._adj, nextlevel, cutoff))
65def _single_shortest_path_length(adj, firstlevel, cutoff):
66 """Yields (node, level) in a breadth first search
68 Shortest Path Length helper function
69 Parameters
70 ----------
71 adj : dict
72 Adjacency dict or view
73 firstlevel : list
74 starting nodes, e.g. [source] or [target]
75 cutoff : int or float
76 level at which we stop the process
77 """
78 seen = set(firstlevel)
79 nextlevel = firstlevel
80 level = 0
81 n = len(adj)
82 for v in nextlevel:
83 yield (v, level)
84 while nextlevel and cutoff > level:
85 level += 1
86 thislevel = nextlevel
87 nextlevel = []
88 for v in thislevel:
89 for w in adj[v]:
90 if w not in seen:
91 seen.add(w)
92 nextlevel.append(w)
93 yield (w, level)
94 if len(seen) == n:
95 return
98@nx._dispatch
99def single_target_shortest_path_length(G, target, cutoff=None):
100 """Compute the shortest path lengths to target from all reachable nodes.
102 Parameters
103 ----------
104 G : NetworkX graph
106 target : node
107 Target node for path
109 cutoff : integer, optional
110 Depth to stop the search. Only paths of length <= cutoff are returned.
112 Returns
113 -------
114 lengths : iterator
115 (source, shortest path length) iterator
117 Examples
118 --------
119 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
120 >>> length = dict(nx.single_target_shortest_path_length(G, 4))
121 >>> length[0]
122 4
123 >>> for node in range(5):
124 ... print(f"{node}: {length[node]}")
125 0: 4
126 1: 3
127 2: 2
128 3: 1
129 4: 0
131 See Also
132 --------
133 single_source_shortest_path_length, shortest_path_length
134 """
135 if target not in G:
136 raise nx.NodeNotFound(f"Target {target} is not in G")
138 msg = "single_target_shortest_path_length will return a dict starting in v3.3"
139 warnings.warn(msg, DeprecationWarning)
141 if cutoff is None:
142 cutoff = float("inf")
143 # handle either directed or undirected
144 adj = G._pred if G.is_directed() else G._adj
145 nextlevel = [target]
146 # for version 3.3 we will return a dict like this:
147 # return dict(_single_shortest_path_length(adj, nextlevel, cutoff))
148 return _single_shortest_path_length(adj, nextlevel, cutoff)
151@nx._dispatch
152def all_pairs_shortest_path_length(G, cutoff=None):
153 """Computes the shortest path lengths between all nodes in `G`.
155 Parameters
156 ----------
157 G : NetworkX graph
159 cutoff : integer, optional
160 Depth at which to stop the search. Only paths of length at most
161 `cutoff` are returned.
163 Returns
164 -------
165 lengths : iterator
166 (source, dictionary) iterator with dictionary keyed by target and
167 shortest path length as the key value.
169 Notes
170 -----
171 The iterator returned only has reachable node pairs.
173 Examples
174 --------
175 >>> G = nx.path_graph(5)
176 >>> length = dict(nx.all_pairs_shortest_path_length(G))
177 >>> for node in [0, 1, 2, 3, 4]:
178 ... print(f"1 - {node}: {length[1][node]}")
179 1 - 0: 1
180 1 - 1: 0
181 1 - 2: 1
182 1 - 3: 2
183 1 - 4: 3
184 >>> length[3][2]
185 1
186 >>> length[2][2]
187 0
189 """
190 length = single_source_shortest_path_length
191 # TODO This can be trivially parallelized.
192 for n in G:
193 yield (n, length(G, n, cutoff=cutoff))
196@nx._dispatch
197def bidirectional_shortest_path(G, source, target):
198 """Returns a list of nodes in a shortest path between source and target.
200 Parameters
201 ----------
202 G : NetworkX graph
204 source : node label
205 starting node for path
207 target : node label
208 ending node for path
210 Returns
211 -------
212 path: list
213 List of nodes in a path from source to target.
215 Raises
216 ------
217 NetworkXNoPath
218 If no path exists between source and target.
220 Examples
221 --------
222 >>> G = nx.Graph()
223 >>> nx.add_path(G, [0, 1, 2, 3, 0, 4, 5, 6, 7, 4])
224 >>> nx.bidirectional_shortest_path(G, 2, 6)
225 [2, 1, 0, 4, 5, 6]
227 See Also
228 --------
229 shortest_path
231 Notes
232 -----
233 This algorithm is used by shortest_path(G, source, target).
234 """
236 if source not in G or target not in G:
237 msg = f"Either source {source} or target {target} is not in G"
238 raise nx.NodeNotFound(msg)
240 # call helper to do the real work
241 results = _bidirectional_pred_succ(G, source, target)
242 pred, succ, w = results
244 # build path from pred+w+succ
245 path = []
246 # from source to w
247 while w is not None:
248 path.append(w)
249 w = pred[w]
250 path.reverse()
251 # from w to target
252 w = succ[path[-1]]
253 while w is not None:
254 path.append(w)
255 w = succ[w]
257 return path
260def _bidirectional_pred_succ(G, source, target):
261 """Bidirectional shortest path helper.
263 Returns (pred, succ, w) where
264 pred is a dictionary of predecessors from w to the source, and
265 succ is a dictionary of successors from w to the target.
266 """
267 # does BFS from both source and target and meets in the middle
268 if target == source:
269 return ({target: None}, {source: None}, source)
271 # handle either directed or undirected
272 if G.is_directed():
273 Gpred = G.pred
274 Gsucc = G.succ
275 else:
276 Gpred = G.adj
277 Gsucc = G.adj
279 # predecessor and successors in search
280 pred = {source: None}
281 succ = {target: None}
283 # initialize fringes, start with forward
284 forward_fringe = [source]
285 reverse_fringe = [target]
287 while forward_fringe and reverse_fringe:
288 if len(forward_fringe) <= len(reverse_fringe):
289 this_level = forward_fringe
290 forward_fringe = []
291 for v in this_level:
292 for w in Gsucc[v]:
293 if w not in pred:
294 forward_fringe.append(w)
295 pred[w] = v
296 if w in succ: # path found
297 return pred, succ, w
298 else:
299 this_level = reverse_fringe
300 reverse_fringe = []
301 for v in this_level:
302 for w in Gpred[v]:
303 if w not in succ:
304 succ[w] = v
305 reverse_fringe.append(w)
306 if w in pred: # found path
307 return pred, succ, w
309 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
312@nx._dispatch
313def single_source_shortest_path(G, source, cutoff=None):
314 """Compute shortest path between source
315 and all other nodes reachable from source.
317 Parameters
318 ----------
319 G : NetworkX graph
321 source : node label
322 Starting node for path
324 cutoff : integer, optional
325 Depth to stop the search. Only paths of length <= cutoff are returned.
327 Returns
328 -------
329 paths : dictionary
330 Dictionary, keyed by target, of shortest paths.
332 Examples
333 --------
334 >>> G = nx.path_graph(5)
335 >>> path = nx.single_source_shortest_path(G, 0)
336 >>> path[4]
337 [0, 1, 2, 3, 4]
339 Notes
340 -----
341 The shortest path is not necessarily unique. So there can be multiple
342 paths between the source and each target node, all of which have the
343 same 'shortest' length. For each target node, this function returns
344 only one of those paths.
346 See Also
347 --------
348 shortest_path
349 """
350 if source not in G:
351 raise nx.NodeNotFound(f"Source {source} not in G")
353 def join(p1, p2):
354 return p1 + p2
356 if cutoff is None:
357 cutoff = float("inf")
358 nextlevel = {source: 1} # list of nodes to check at next level
359 paths = {source: [source]} # paths dictionary (paths to key from source)
360 return dict(_single_shortest_path(G.adj, nextlevel, paths, cutoff, join))
363def _single_shortest_path(adj, firstlevel, paths, cutoff, join):
364 """Returns shortest paths
366 Shortest Path helper function
367 Parameters
368 ----------
369 adj : dict
370 Adjacency dict or view
371 firstlevel : dict
372 starting nodes, e.g. {source: 1} or {target: 1}
373 paths : dict
374 paths for starting nodes, e.g. {source: [source]}
375 cutoff : int or float
376 level at which we stop the process
377 join : function
378 function to construct a path from two partial paths. Requires two
379 list inputs `p1` and `p2`, and returns a list. Usually returns
380 `p1 + p2` (forward from source) or `p2 + p1` (backward from target)
381 """
382 level = 0 # the current level
383 nextlevel = firstlevel
384 while nextlevel and cutoff > level:
385 thislevel = nextlevel
386 nextlevel = {}
387 for v in thislevel:
388 for w in adj[v]:
389 if w not in paths:
390 paths[w] = join(paths[v], [w])
391 nextlevel[w] = 1
392 level += 1
393 return paths
396@nx._dispatch
397def single_target_shortest_path(G, target, cutoff=None):
398 """Compute shortest path to target from all nodes that reach target.
400 Parameters
401 ----------
402 G : NetworkX graph
404 target : node label
405 Target node for path
407 cutoff : integer, optional
408 Depth to stop the search. Only paths of length <= cutoff are returned.
410 Returns
411 -------
412 paths : dictionary
413 Dictionary, keyed by target, of shortest paths.
415 Examples
416 --------
417 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
418 >>> path = nx.single_target_shortest_path(G, 4)
419 >>> path[0]
420 [0, 1, 2, 3, 4]
422 Notes
423 -----
424 The shortest path is not necessarily unique. So there can be multiple
425 paths between the source and each target node, all of which have the
426 same 'shortest' length. For each target node, this function returns
427 only one of those paths.
429 See Also
430 --------
431 shortest_path, single_source_shortest_path
432 """
433 if target not in G:
434 raise nx.NodeNotFound(f"Target {target} not in G")
436 def join(p1, p2):
437 return p2 + p1
439 # handle undirected graphs
440 adj = G.pred if G.is_directed() else G.adj
441 if cutoff is None:
442 cutoff = float("inf")
443 nextlevel = {target: 1} # list of nodes to check at next level
444 paths = {target: [target]} # paths dictionary (paths to key from source)
445 return dict(_single_shortest_path(adj, nextlevel, paths, cutoff, join))
448@nx._dispatch
449def all_pairs_shortest_path(G, cutoff=None):
450 """Compute shortest paths between all nodes.
452 Parameters
453 ----------
454 G : NetworkX graph
456 cutoff : integer, optional
457 Depth at which to stop the search. Only paths of length at most
458 `cutoff` are returned.
460 Returns
461 -------
462 paths : iterator
463 Dictionary, keyed by source and target, of shortest paths.
465 Examples
466 --------
467 >>> G = nx.path_graph(5)
468 >>> path = dict(nx.all_pairs_shortest_path(G))
469 >>> print(path[0][4])
470 [0, 1, 2, 3, 4]
472 Notes
473 -----
474 There may be multiple shortest paths with the same length between
475 two nodes. For each pair, this function returns only one of those paths.
477 See Also
478 --------
479 floyd_warshall
480 all_pairs_all_shortest_paths
482 """
483 # TODO This can be trivially parallelized.
484 for n in G:
485 yield (n, single_source_shortest_path(G, n, cutoff=cutoff))
488@nx._dispatch
489def predecessor(G, source, target=None, cutoff=None, return_seen=None):
490 """Returns dict of predecessors for the path from source to all nodes in G.
492 Parameters
493 ----------
494 G : NetworkX graph
496 source : node label
497 Starting node for path
499 target : node label, optional
500 Ending node for path. If provided only predecessors between
501 source and target are returned
503 cutoff : integer, optional
504 Depth to stop the search. Only paths of length <= cutoff are returned.
506 return_seen : bool, optional (default=None)
507 Whether to return a dictionary, keyed by node, of the level (number of
508 hops) to reach the node (as seen during breadth-first-search).
510 Returns
511 -------
512 pred : dictionary
513 Dictionary, keyed by node, of predecessors in the shortest path.
516 (pred, seen): tuple of dictionaries
517 If `return_seen` argument is set to `True`, then a tuple of dictionaries
518 is returned. The first element is the dictionary, keyed by node, of
519 predecessors in the shortest path. The second element is the dictionary,
520 keyed by node, of the level (number of hops) to reach the node (as seen
521 during breadth-first-search).
523 Examples
524 --------
525 >>> G = nx.path_graph(4)
526 >>> list(G)
527 [0, 1, 2, 3]
528 >>> nx.predecessor(G, 0)
529 {0: [], 1: [0], 2: [1], 3: [2]}
530 >>> nx.predecessor(G, 0, return_seen=True)
531 ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})
534 """
535 if source not in G:
536 raise nx.NodeNotFound(f"Source {source} not in G")
538 level = 0 # the current level
539 nextlevel = [source] # list of nodes to check at next level
540 seen = {source: level} # level (number of hops) when seen in BFS
541 pred = {source: []} # predecessor dictionary
542 while nextlevel:
543 level = level + 1
544 thislevel = nextlevel
545 nextlevel = []
546 for v in thislevel:
547 for w in G[v]:
548 if w not in seen:
549 pred[w] = [v]
550 seen[w] = level
551 nextlevel.append(w)
552 elif seen[w] == level: # add v to predecessor list if it
553 pred[w].append(v) # is at the correct level
554 if cutoff and cutoff <= level:
555 break
557 if target is not None:
558 if return_seen:
559 if target not in pred:
560 return ([], -1) # No predecessor
561 return (pred[target], seen[target])
562 else:
563 if target not in pred:
564 return [] # No predecessor
565 return pred[target]
566 else:
567 if return_seen:
568 return (pred, seen)
569 else:
570 return pred