networkx.path

1 # -*- coding: utf-8 -*- 2 """ 3 Shortest path algorithms. 4 """ 5 __author__ = """Aric Hagberg (hagberg@lanl.gov)""" 6 ___revision__ = "" 7 # Copyright (C) 2004-2006 by 8 # Aric Hagberg <hagberg@lanl.gov> 9 # Dan Schult <dschult@colgate.edu> 10 # Pieter Swart <swart@lanl.gov> 11 # Distributed under the terms of the GNU Lesser General Public License 12 # http://www.gnu.org/copyleft/lesser.html 13 import networkx 14 #use deque only if networkx requires python 2.4 15 #from collections import deque 16 import heapq 17 18

19 -def shortest_path_length(G,source,target):

20 """Return the shortest path length in the graph G between 21 the source and target. Raise an exception if no path exists. 22 23 G is treated as an unweighted graph. For weighted graphs 24 see dijkstra_path_length. 25 """ 26 path=bidirectional_shortest_path(G,source,target) 27 if path is False: 28 raise networkx.NetworkXError,\ 29 "no path from %s to %s"%(source,target) 30 return len(path)-1

31

32 -def single_source_shortest_path_length(G,source,cutoff=None):

33 """ 34 Shortest path length from source to all reachable nodes. 35 36 Returns a dictionary of shortest path lengths keyed by target. 37 38 >>> G=path_graph(5) 39 >>> length=single_source_shortest_path_length(G,1) 40 >>> length[4] 41 3 42 >>> print length 43 {0: 1, 1: 0, 2: 1, 3: 2, 4: 3} 44 45 cutoff is optional integer depth to stop the search - only 46 paths of length <= cutoff are returned. 47 48 """ 49 seen={} # level (number of hops) when seen in BFS 50 level=0 # the current level 51 nextlevel={source:1} # dict of nodes to check at next level 52 while nextlevel: 53 thislevel=nextlevel # advance to next level 54 nextlevel={} # and start a new list (fringe) 55 for v in thislevel: 56 if not seen.has_key(v): 57 seen[v]=level # set the level of vertex v 58 nbrs=dict.fromkeys(G.neighbors_iter(v),1) 59 nextlevel.update(nbrs) # add neighbors of v 60 if (cutoff is not None and cutoff <= level): break 61 level=level+1 62 return seen # return all path lengths as dictionary

63 64

65 -def all_pairs_shortest_path_length(G,cutoff=None):

66 """ Return dictionary of shortest path lengths between all nodes in G. 67 68 The dictionary only has keys for reachable node pairs. 69 >>> G=path_graph(5) 70 >>> length=all_pairs_shortest_path_length(G) 71 >>> print length[1][4] 72 3 73 >>> length[1] 74 {0: 1, 1: 0, 2: 1, 3: 2, 4: 3} 75 76 77 cutoff is optional integer depth to stop the search - only 78 paths of length <= cutoff are returned. 79 80 """ 81 paths={} 82 for n in G: 83 paths[n]=single_source_shortest_path_length(G,n,cutoff=cutoff) 84 return paths

85

86 -def shortest_path(G,source,target):

87 """Return a list of nodes in G for a shortest path between source 88 and target. 89 90 There may be more than one shortest path. This returns only one. 91 92 """ 93 return bidirectional_shortest_path(G,source,target)

94 95

96 -def bidirectional_shortest_path(G,source,target):

97 """ 98 Return list of nodes in a shortest path between source and target. 99 Return False if no path exists. 100 101 Also known as shortest_path. 102 103 """ 104 # call helper to do the real work 105 results=_bidirectional_pred_succ(G,source,target) 106 if results is False: 107 return False # no path from source to target 108 pred,succ,w=results 109 110 # build path from pred+w+succ 111 path=[] 112 # from w to target 113 while w is not None: 114 path.append(w) 115 w=succ[w] 116 # from source to w 117 w=pred[path[0]] 118 while w is not None: 119 path.insert(0,w) 120 w=pred[w] 121 122 return path

123

124 -def _bidirectional_pred_succ(G, source, target):

125 """ 126 Bidirectional shortest path helper. 127 128 Returns (pred,succ,w) where 129 pred is a dictionary of predecessors from w to the source, and 130 succ is a dictionary of successors from w to the target. 131 """ 132 # does BFS from both source and target and meets in the middle 133 if source is None or target is None: 134 raise NetworkXException(\ 135 "Bidirectional shortest path called without source or target") 136 if target == source: return ({1:None},{1:None},1) 137 138 # handle either directed or undirected 139 if G.is_directed(): 140 Gpred=G.predecessors_iter 141 Gsucc=G.successors_iter 142 else: 143 Gpred=G.neighbors_iter 144 Gsucc=G.neighbors_iter 145 146 # predecesssor and successors in search 147 pred={source:None} 148 succ={target:None} 149 150 # initialize fringes, start with forward 151 forward_fringe=[source] 152 reverse_fringe=[target] 153 154 while forward_fringe and reverse_fringe: 155 this_level=forward_fringe 156 forward_fringe=[] 157 for v in this_level: 158 for w in Gsucc(v): 159 if w not in pred: 160 forward_fringe.append(w) 161 pred[w]=v 162 if w in succ: return pred,succ,w # found path 163 this_level=reverse_fringe 164 reverse_fringe=[] 165 for v in this_level: 166 for w in Gpred(v): 167 if w not in succ: 168 succ[w]=v 169 reverse_fringe.append(w) 170 if w in pred: return pred,succ,w # found path 171 172 return False # no path found

173 174

175 -def single_source_shortest_path(G,source,cutoff=None):

176 """ 177 Return list of nodes in a shortest path between source 178 and all other nodes in G reachable from source. 179 180 There may be more than one shortest path between the 181 source and target nodes - this routine returns only one. 182 183 cutoff is optional integer depth to stop the search - only 184 paths of length <= cutoff are returned. 185 186 See also shortest_path and bidirectional_shortest_path. 187 """ 188 level=0 # the current level 189 nextlevel={source:1} # list of nodes to check at next level 190 paths={source:[source]} # paths dictionary (paths to key from source) 191 if cutoff==0: 192 return paths 193 while nextlevel: 194 thislevel=nextlevel 195 nextlevel={} 196 for v in thislevel: 197 for w in G.neighbors(v): 198 if not paths.has_key(w): 199 paths[w]=paths[v]+[w] 200 nextlevel[w]=1 201 level=level+1 202 if (cutoff is not None and cutoff <= level): break 203 return paths

204 205

206 -def all_pairs_shortest_path(G,cutoff=None):

207 """ Return dictionary of shortest paths between all nodes in G. 208 209 The dictionary only has keys for reachable node pairs. 210 211 cutoff is optional integer depth to stop the search - only 212 paths of length <= cutoff are returned. 213 214 See also floyd_warshall. 215 216 """ 217 paths={} 218 for n in G: 219 paths[n]=single_source_shortest_path(G,n,cutoff=cutoff) 220 return paths

221 222

223 -def dijkstra_path(G,source,target):

224 """ 225 Returns the shortest path from source to target in a weighted 226 graph G. Uses a bidirectional version of Dijkstra's algorithm. 227 228 Edge data must be numerical values for XGraph and XDiGraphs. 229 The weights are assigned to be 1 for Graphs and DiGraphs. 230 231 See also bidirectional_dijkstra for more information about the algorithm. 232 """ 233 # (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test 234 # return path 235 (length,path)=single_source_dijkstra(G,source) 236 try: 237 return path[target] 238 except KeyError: 239 raise networkx.NetworkXError, \ 240 "node %s not reachable from %s"%(source,target)

241 242

243 -def dijkstra_path_length(G,source,target):

244 """ 245 Returns the shortest path length from source to target in a weighted 246 graph G. Uses a bidirectional version of Dijkstra's algorithm. 247 248 Edge data must be numerical values for XGraph and XDiGraphs. 249 The weights are assigned to be 1 for Graphs and DiGraphs. 250 251 See also bidirectional_dijkstra for more information about the algorithm. 252 253 """ 254 255 # (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test 256 # return length 257 (length,path)=single_source_dijkstra(G,source) 258 try: 259 return length[target] 260 except KeyError: 261 raise networkx.NetworkXError, \ 262 "node %s not reachable from %s"%(source,target)

263 264 265

266 -def bidirectional_dijkstra(G, source, target):

267 """ 268 Dijkstra's algorithm for shortest paths using bidirectional search. 269 270 Returns a two-tuple (d,p) where d is the distance and p 271 is the path from the source to the target. 272 273 Distances are calculated as sums of weighted edges traversed. 274 275 Edges must hold numerical values for XGraph and XDiGraphs. 276 The weights are set to 1 for Graphs and DiGraphs. 277 278 In practice bidirectional Dijkstra is much more than twice as fast as 279 ordinary Dijkstra. 280 281 Ordinary Dijkstra expands nodes in a sphere-like manner from the 282 source. The radius of this sphere will eventually be the length 283 of the shortest path. Bidirectional Dijkstra will expand nodes 284 from both the source and the target, making two spheres of half 285 this radius. Volume of the first sphere is pi*r*r while the 286 others are 2*pi*r/2*r/2, making up half the volume. 287 288 This algorithm is not guaranteed to work if edge weights 289 are negative or are floating point numbers 290 (overflows and roundoff errors can cause problems). 291 292 """ 293 if source is None or target is None: 294 raise NetworkXException( 295 "Bidirectional Dijkstra called with no source or target") 296 if source == target: return (0, [source]) 297 #Init: Forward Backward 298 dists = [{}, {}]# dictionary of final distances 299 paths = [{source:[source]}, {target:[target]}] # dictionary of paths 300 fringe = [[], []] #heap of (distance, node) tuples for extracting next node to expand 301 seen = [{source:0}, {target:0} ]#dictionary of distances to nodes seen 302 #initialize fringe heap 303 heapq.heappush(fringe[0], (0, source)) 304 heapq.heappush(fringe[1], (0, target)) 305 #neighs for extracting correct neighbor information 306 if G.is_directed(): 307 neighs = [G.successors_iter, G.predecessors_iter] 308 else: 309 neighs = [G.neighbors_iter, G.neighbors_iter] 310 #variables to hold shortest discovered path 311 #finaldist = 1e30000 312 finalpath = [] 313 # if unweighted graph, set the weights to 1 on edges by 314 # introducing a get_edge method 315 if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1 316 dir = 1 317 while fringe[0] and fringe[1]: 318 # choose direction 319 # dir == 0 is forward direction and dir == 1 is back 320 dir = 1-dir 321 # extract closest to expand 322 (dist, v )= heapq.heappop(fringe[dir]) 323 if v in dists[dir]: 324 # Shortest path to v has already been found 325 continue 326 # update distance 327 dists[dir][v] = dist #equal to seen[dir][v] 328 if v in dists[1-dir]: 329 # if we have scanned v in both directions we are done 330 # we have now discovered the shortest path 331 return (finaldist,finalpath) 332 for w in neighs[dir](v): 333 if(dir==0): #forward 334 vwLength = dists[dir][v] + G.get_edge(v,w) 335 else: #back, must remember to change v,w->w,v 336 vwLength = dists[dir][v] + G.get_edge(w,v) 337 338 if w in dists[dir]: 339 if vwLength < dists[dir][w]: 340 raise ValueError,\ 341 "Contradictory paths found: negative weights?" 342 elif w not in seen[dir] or vwLength < seen[dir][w]: 343 # relaxing 344 seen[dir][w] = vwLength 345 heapq.heappush(fringe[dir], (vwLength,w)) 346 paths[dir][w] = paths[dir][v]+[w] 347 if w in seen[0] and w in seen[1]: 348 #see if this path is better than than the already 349 #discovered shortest path 350 totaldist = seen[0][w] + seen[1][w] 351 if finalpath == [] or finaldist > totaldist: 352 finaldist = totaldist 353 revpath = paths[1][w][:] 354 revpath.reverse() 355 finalpath = paths[0][w] + revpath[1:] 356 return False

357 358 359 #def dijkstra(G,source,target): 360 # return bidirectional_dijkstra(G,source,target) 361 362

363 -def single_source_dijkstra_path(G,source):

364 """ 365 Returns the shortest paths from source to all other reachable 366 nodes in a weighted graph G. Uses Dijkstra's algorithm. 367 368 Returns a dictionary of shortest path lengths keyed by source. 369 370 Edge data must be numerical values for XGraph and XDiGraphs. 371 The weights are assigned to be 1 for Graphs and DiGraphs. 372 373 See also single_source_dijkstra for more information about the algorithm. 374 375 """ 376 (length,path)=single_source_dijkstra(G,source) 377 return path

378 379

380 -def single_source_dijkstra_path_length(G,source):

381 """ 382 Returns the shortest path lengths from source to all other 383 reachable nodes in a weighted graph G. Uses Dijkstra's algorithm. 384 385 Returns a dictionary of shortest path lengths keyed by source. 386 387 Edge data must be numerical values for XGraph and XDiGraphs. 388 The weights are assigned to be 1 for Graphs and DiGraphs. 389 390 See also single_source_dijkstra for more information about the algorithm. 391 392 """ 393 (length,path)=single_source_dijkstra(G,source) 394 return length

395 396

397 -def single_source_dijkstra(G,source,target=None):

398 """ 399 Dijkstra's algorithm for shortest paths in a weighted graph G. 400 401 Use: 402 403 single_source_dijkstra_path() - shortest path list of nodes 404 405 single_source_dijkstra_path_length() - shortest path length 406 407 Returns a tuple of two dictionaries keyed by node. 408 The first stores distance from the source. 409 The second stores the path from the source to that node. 410 411 Distances are calculated as sums of weighted edges traversed. 412 Edges must hold numerical values for XGraph and XDiGraphs. 413 The weights are 1 for Graphs and DiGraphs. 414 415 Optional target argument stops the search when target is found. 416 417 Based on the Python cookbook recipe (119466) at 418 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466 419 420 This algorithm is not guaranteed to work if edge weights 421 are negative or are floating point numbers 422 (overflows and roundoff errors can cause problems). 423 424 See also 'bidirectional_dijkstra_path' 425 """ 426 if source==target: return (0, [source]) 427 dist = {} # dictionary of final distances 428 paths = {source:[source]} # dictionary of paths 429 seen = {source:0} 430 fringe=[] # use heapq with (distance,label) tuples 431 heapq.heappush(fringe,(0,source)) 432 while fringe: 433 (d,v)=heapq.heappop(fringe) 434 if v in dist: continue # already searched this node. 435 dist[v] = seen[v] 436 if v == target: break 437 for w in G.neighbors(v): 438 vw_dist = dist[v] + G.get_edge(v,w) 439 if w in dist: 440 if vw_dist < dist[w]: 441 raise ValueError,\ 442 "Contradictory paths found: negative weights?" 443 elif w not in seen or vw_dist < seen[w]: 444 seen[w] = vw_dist 445 heapq.heappush(fringe,(vw_dist,w)) 446 paths[w] = paths[v]+[w] 447 return (dist,paths)

448

449 -def dijkstra_predecessor_and_distance(G,source):

450 """ 451 Same algorithm as for single_source_dijsktra, but returns two 452 dicts representing a list of predecessors of a node and the 453 distance to each node respectively. The list of predecessors 454 contains more than one element only when there are more than one 455 shortest paths to the key node. 456 457 This routine is intended for use with the betweenness centrality 458 algorithms in centrality.py. 459 """ 460 push=heapq.heappush 461 pop=heapq.heappop 462 dist = {} # dictionary of final distances 463 pred = {source:[]} # dictionary of predecessors 464 seen = {source:0} 465 fringe=[] # use heapq with (distance,label) tuples 466 push(fringe,(0,source)) 467 while fringe: 468 (d,v)=pop(fringe) 469 if v in dist: continue # already searched this node. 470 dist[v] = seen[v] 471 for w in G.neighbors(v): 472 vw_dist = dist[v] + G.get_edge(v,w) 473 if w in dist: 474 if vw_dist < dist[w]: 475 raise ValueError,\ 476 "Contradictory paths found: negative weights?" 477 elif w not in seen or vw_dist < seen[w]: 478 seen[w] = vw_dist 479 push(fringe,(vw_dist,w)) 480 pred[w] = [v] 481 elif vw_dist==seen[w]: 482 pred[w].append(v) 483 return (pred,dist)

484 485 ###################################################################### 486 ### Jeff A mods. Kept very local for now. 487

488 -def floyd_warshall_array(graph):

489 """ 490 The Floyd-Warshall algorithm for all pairs shortest paths. 491 492 Returns a tuple (distance,path) containing two arrays of shortest 493 distance and paths as a predecessor matrix. 494 495 This differs from 496 floyd_warshall only in the types of the return values. Thus, 497 path[i,j] gives the predecessor at j on a path from i to j. A 498 value of None indicates that no path exists. A predecessor of i 499 indicates the beginning of the path. The advantage of this 500 implementation is that, while running time is O(n^3), running 501 space is O(n^2). 502 503 This algorithm handles negative weights. 504 """ 505 506 # A weight that's more than any path weight 507 HUGE_VAL = 1 508 for e in graph.edges(): 509 HUGE_VAL += abs(graph.get_edge(e[0],e[1])) 510 511 dist = {} 512 dist_prev = {} 513 pred = {} 514 pred_prev = {} 515 for i in graph: 516 dist[i] = {} 517 dist_prev[i] = {} 518 pred[i] = {} 519 pred_prev[i] = {} 520 for j in graph: 521 dist[i][j] = 0 # arbitrary, just create slot 522 pred[i][j] = 0 # arbitrary, just create slot 523 if i == j: 524 dist_prev[i][j] = 0 525 pred_prev[i][j] = -1 526 elif graph.has_edge(i,j): 527 val = graph.get_edge(i,j) 528 dist_prev[i][j] = val 529 pred_prev[i][j] = i 530 else: 531 # no edge, distinct vertices 532 dist_prev[i][j] = HUGE_VAL 533 pred_prev[i][j] = -1 # None, but has to be numerically comparable 534 for k in graph: 535 for i in graph: 536 for j in graph: 537 dist[i][j] = min(dist_prev[i][j], dist_prev[i][k] + dist_prev[k][j]) 538 if dist_prev[i][j] <= dist_prev[i][k] + dist[k][j]: 539 pred[i][j] = pred_prev[i][j] 540 else: 541 pred[i][j] = pred_prev[k][j] 542 tmp = dist_prev 543 dist_prev = dist 544 dist = tmp 545 546 tmp = pred_prev 547 pred_prev = pred 548 pred = tmp 549 # The last time through the loop, we exchanged for nothing, so 550 # return the prev versions, since they're really the current 551 # versions. 552 return dist_prev, pred_prev

553 ###################################################################### 554

555 -def floyd_warshall(G,huge=1e30000):

556 """ 557 The Floyd-Warshall algorithm for all pairs shortest paths. 558 559 Returns a tuple (distance,path) containing two dictionaries of shortest 560 distance and predecessor paths. 561 562 This algorithm is most appropriate for dense graphs. 563 The running time is O(n^3), and running space is O(n^2) 564 where n is the number of nodes in G. 565 566 For sparse graphs, see 567 568 all_pairs_shortest_path 569 all_pairs_shortest_path_length 570 571 which are based on Dijkstra's algorithm. 572 573 """ 574 # dictionary-of-dictionaries representation for dist and pred 575 dist={} 576 # initialize path distance dictionary to be the adjacency matrix 577 # but with sentinal value "huge" where there is no edge 578 # also set the distance to self to 0 (zero diagonal) 579 pred={} 580 # initialize predecessor dictionary 581 for u in G.nodes(): 582 dist[u]={} 583 pred[u]={} 584 for v in G.nodes(): 585 if G.has_edge(u,v): 586 dist[u][v]=G.get_edge(u,v) 587 pred[u][v]=u 588 else: 589 dist[u][v]=huge 590 pred[u][v]=None 591 dist[u][u]=0 # set 0 distance to self 592 593 for w in G.nodes(): 594 for u in G.nodes(): 595 for v in G.nodes(): 596 if dist[u][v] > dist[u][w] + dist[w][v]: 597 dist[u][v] = dist[u][w] + dist[w][v] 598 pred[u][v] = pred[w][v] 599 return dist,pred

600 601

602 -def predecessor(G,source,target=None,cutoff=None,return_seen=None):

603 """ Returns dictionary of predecessors for the path from source to all 604 nodes in G. 605 606 Optional target returns only predecessors between source and target. 607 Cutoff is a limit on the number of hops traversed. 608 609 Example for the path graph 0-1-2-3 610 611 >>> G=path_graph(4) 612 >>> print G.nodes() 613 [0, 1, 2, 3] 614 >>> predecessor(G,0) 615 {0: [], 1: [0], 2: [1], 3: [2]} 616 617 """ 618 level=0 # the current level 619 nextlevel=[source] # list of nodes to check at next level 620 seen={source:level} # level (number of hops) when seen in BFS 621 pred={source:[]} # predecessor dictionary 622 while nextlevel: 623 level=level+1 624 thislevel=nextlevel 625 nextlevel=[] 626 for v in thislevel: 627 for w in G.neighbors(v): 628 if (not seen.has_key(w)): 629 pred[w]=[v] 630 seen[w]=level 631 nextlevel.append(w) 632 elif (seen[w]==level):# add v to predecessor list if it 633 pred[w].append(v) # is at the correct level 634 if (cutoff and cutoff <= level): 635 break 636 637 if target is not None: 638 if return_seen: 639 if not pred.has_key(target): return ([],-1) # No predecessor 640 return (pred[target],seen[target]) 641 else: 642 if not pred.has_key(target): return [] # No predecessor 643 return pred[target] 644 else: 645 if return_seen: 646 return (pred,seen) 647 else: 648 return pred

649 650

651 -def _test_suite():

652 import doctest 653 suite = doctest.DocFileSuite('tests/shortest_path.txt',package='networkx') 654 return suite

655 656 657 if __name__ == "__main__": 658 import os 659 import sys 660 import unittest 661 if sys.version_info[:2] < (2, 4): 662 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 663 sys.exit(-1) 664 # directory of networkx package (relative to this) 665 nxbase=sys.path[0]+os.sep+os.pardir 666 sys.path.insert(0,nxbase) # prepend to search path 667 unittest.TextTestRunner().run(_test_suite()) 668

Source Code for Module networkx.path