ioftools / networkxMiCe / networkxmaster / networkx / algorithms / simple_paths.py @ 5cef0f13
History  View  Annotate  Download (25.5 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 2012 by

3 
# Sergio Nery Simoes <sergionery@gmail.com>

4 
# All rights reserved.

5 
# BSD license.

6 
import collections 
7 
from heapq import heappush, heappop 
8 
from itertools import count 
9  
10 
import networkx as nx 
11 
from networkx.utils import not_implemented_for 
12 
from networkx.utils import pairwise 
13  
14 
__author__ = """\n""".join(['Sérgio Nery Simões <sergionery@gmail.com>', 
15 
'Aric Hagberg <aric.hagberg@gmail.com>',

16 
'Andrey Paramonov',

17 
'Jordi Torrents <jordi.t21@gmail.com>'])

18  
19 
__all__ = [ 
20 
'all_simple_paths',

21 
'is_simple_path',

22 
'shortest_simple_paths',

23 
] 
24  
25  
26 
def is_simple_path(G, nodes): 
27 
"""Returns True if and only if the given nodes form a simple path in

28 
`G`.

29 

30 
A *simple path* in a graph is a nonempty sequence of nodes in which

31 
no node appears more than once in the sequence, and each adjacent

32 
pair of nodes in the sequence is adjacent in the graph.

33 

34 
Parameters

35 


36 
nodes : list

37 
A list of one or more nodes in the graph `G`.

38 

39 
Returns

40 


41 
bool

42 
Whether the given list of nodes represents a simple path in

43 
`G`.

44 

45 
Notes

46 


47 
A list of zero nodes is not a path and a list of one node is a

48 
path. Here's an explanation why.

49 

50 
This function operates on *node paths*. One could also consider

51 
*edge paths*. There is a bijection between node paths and edge

52 
paths.

53 

54 
The *length of a path* is the number of edges in the path, so a list

55 
of nodes of length *n* corresponds to a path of length *n*  1.

56 
Thus the smallest edge path would be a list of zero edges, the empty

57 
path. This corresponds to a list of one node.

58 

59 
To convert between a node path and an edge path, you can use code

60 
like the following::

61 

62 
>>> from networkx.utils import pairwise

63 
>>> nodes = [0, 1, 2, 3]

64 
>>> edges = list(pairwise(nodes))

65 
>>> edges

66 
[(0, 1), (1, 2), (2, 3)]

67 
>>> nodes = [edges[0][0]] + [v for u, v in edges]

68 
>>> nodes

69 
[0, 1, 2, 3]

70 

71 
Examples

72 


73 
>>> G = nx.cycle_graph(4)

74 
>>> nx.is_simple_path(G, [2, 3, 0])

75 
True

76 
>>> nx.is_simple_path(G, [0, 2])

77 
False

78 

79 
"""

80 
# The empty list is not a valid path. Could also return

81 
# NetworkXPointlessConcept here.

82 
if len(nodes) == 0: 
83 
return False 
84 
# If the list is a single node, just check that the node is actually

85 
# in the graph.

86 
if len(nodes) == 1: 
87 
return nodes[0] in G 
88 
# Test that no node appears more than once, and that each

89 
# adjacent pair of nodes is adjacent.

90 
return (len(set(nodes)) == len(nodes) and 
91 
all(v in G[u] for u, v in pairwise(nodes))) 
92  
93  
94 
def all_simple_paths(G, source, target, cutoff=None): 
95 
"""Generate all simple paths in the graph G from source to target.

96 

97 
A simple path is a path with no repeated nodes.

98 

99 
Parameters

100 


101 
G : NetworkX graph

102 

103 
source : node

104 
Starting node for path

105 

106 
target : nodes

107 
Single node or iterable of nodes at which to end path

108 

109 
cutoff : integer, optional

110 
Depth to stop the search. Only paths of length <= cutoff are returned.

111 

112 
Returns

113 


114 
path_generator: generator

115 
A generator that produces lists of simple paths. If there are no paths

116 
between the source and target within the given cutoff the generator

117 
produces no output.

118 

119 
Examples

120 


121 
This iterator generates lists of nodes::

122 

123 
>>> G = nx.complete_graph(4)

124 
>>> for path in nx.all_simple_paths(G, source=0, target=3):

125 
... print(path)

126 
...

127 
[0, 1, 2, 3]

128 
[0, 1, 3]

129 
[0, 2, 1, 3]

130 
[0, 2, 3]

131 
[0, 3]

132 

133 
You can generate only those paths that are shorter than a certain

134 
length by using the `cutoff` keyword argument::

135 

136 
>>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2)

137 
>>> print(list(paths))

138 
[[0, 1, 3], [0, 2, 3], [0, 3]]

139 

140 
To get each path as the corresponding list of edges, you can use the

141 
:func:`networkx.utils.pairwise` helper function::

142 

143 
>>> paths = nx.all_simple_paths(G, source=0, target=3)

144 
>>> for path in map(nx.utils.pairwise, paths):

145 
... print(list(path))

146 
[(0, 1), (1, 2), (2, 3)]

147 
[(0, 1), (1, 3)]

148 
[(0, 2), (2, 1), (1, 3)]

149 
[(0, 2), (2, 3)]

150 
[(0, 3)]

151 

152 
Pass an iterable of nodes as target to generate all paths ending in any of several nodes::

153 

154 
>>> G = nx.complete_graph(4)

155 
>>> for path in nx.all_simple_paths(G, source=0, target=[3, 2]):

156 
... print(path)

157 
...

158 
[0, 1, 2]

159 
[0, 1, 2, 3]

160 
[0, 1, 3]

161 
[0, 1, 3, 2]

162 
[0, 2]

163 
[0, 2, 1, 3]

164 
[0, 2, 3]

165 
[0, 3]

166 
[0, 3, 1, 2]

167 
[0, 3, 2]

168 

169 
Iterate over each path from the root nodes to the leaf nodes in a

170 
directed acyclic graph using a functional programming approach::

171 

172 
>>> from itertools import chain

173 
>>> from itertools import product

174 
>>> from itertools import starmap

175 
>>> from functools import partial

176 
>>>

177 
>>> chaini = chain.from_iterable

178 
>>>

179 
>>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])

180 
>>> roots = (v for v, d in G.in_degree() if d == 0)

181 
>>> leaves = (v for v, d in G.out_degree() if d == 0)

182 
>>> all_paths = partial(nx.all_simple_paths, G)

183 
>>> list(chaini(starmap(all_paths, product(roots, leaves))))

184 
[[0, 1, 2], [0, 3, 2]]

185 

186 
The same list computed using an iterative approach::

187 

188 
>>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])

189 
>>> roots = (v for v, d in G.in_degree() if d == 0)

190 
>>> leaves = (v for v, d in G.out_degree() if d == 0)

191 
>>> all_paths = []

192 
>>> for root in roots:

193 
... for leaf in leaves:

194 
... paths = nx.all_simple_paths(G, root, leaf)

195 
... all_paths.extend(paths)

196 
>>> all_paths

197 
[[0, 1, 2], [0, 3, 2]]

198 

199 
Iterate over each path from the root nodes to the leaf nodes in a

200 
directed acyclic graph passing all leaves together to avoid unnecessary

201 
compute::

202 

203 
>>> G = nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)])

204 
>>> roots = (v for v, d in G.in_degree() if d == 0)

205 
>>> leaves = [v for v, d in G.out_degree() if d == 0]

206 
>>> all_paths = []

207 
>>> for root in roots:

208 
... paths = nx.all_simple_paths(G, root, leaves)

209 
... all_paths.extend(paths)

210 
>>> all_paths

211 
[[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]]

212 

213 
Notes

214 


215 
This algorithm uses a modified depthfirst search to generate the

216 
paths [1]_. A single path can be found in $O(V+E)$ time but the

217 
number of simple paths in a graph can be very large, e.g. $O(n!)$ in

218 
the complete graph of order $n$.

219 

220 
References

221 


222 
.. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",

223 
Addison Wesley Professional, 3rd ed., 2001.

224 

225 
See Also

226 


227 
all_shortest_paths, shortest_path

228 

229 
"""

230 
if source not in G: 
231 
raise nx.NodeNotFound('source node %s not in graph' % source) 
232 
if target in G: 
233 
targets = {target} 
234 
else:

235 
try:

236 
targets = set(target)

237 
except TypeError: 
238 
raise nx.NodeNotFound('target node %s not in graph' % target) 
239 
if source in targets: 
240 
return []

241 
if cutoff is None: 
242 
cutoff = len(G)  1 
243 
if cutoff < 1: 
244 
return []

245 
if G.is_multigraph():

246 
return _all_simple_paths_multigraph(G, source, targets, cutoff)

247 
else:

248 
return _all_simple_paths_graph(G, source, targets, cutoff)

249  
250  
251 
def _all_simple_paths_graph(G, source, targets, cutoff): 
252 
visited = collections.OrderedDict.fromkeys([source]) 
253 
stack = [iter(G[source])]

254 
while stack:

255 
children = stack[1]

256 
child = next(children, None) 
257 
if child is None: 
258 
stack.pop() 
259 
visited.popitem() 
260 
elif len(visited) < cutoff: 
261 
if child in visited: 
262 
continue

263 
if child in targets: 
264 
yield list(visited) + [child] 
265 
visited[child] = None

266 
if targets  set(visited.keys()): # expand stack until find all targets 
267 
stack.append(iter(G[child]))

268 
else:

269 
visited.popitem() # maybe other ways to child

270 
else: # len(visited) == cutoff: 
271 
for target in (targets & (set(children)  {child}))  set(visited.keys()): 
272 
yield list(visited) + [target] 
273 
stack.pop() 
274 
visited.popitem() 
275  
276  
277 
def _all_simple_paths_multigraph(G, source, targets, cutoff): 
278 
visited = collections.OrderedDict.fromkeys([source]) 
279 
stack = [(v for u, v in G.edges(source))] 
280 
while stack:

281 
children = stack[1]

282 
child = next(children, None) 
283 
if child is None: 
284 
stack.pop() 
285 
visited.popitem() 
286 
elif len(visited) < cutoff: 
287 
if child in visited: 
288 
continue

289 
if child in targets: 
290 
yield list(visited) + [child] 
291 
visited[child] = None

292 
if targets  set(visited.keys()): 
293 
stack.append((v for u, v in G.edges(child))) 
294 
else:

295 
visited.popitem() 
296 
else: # len(visited) == cutoff: 
297 
for target in targets  set(visited.keys()): 
298 
count = ([child] + list(children)).count(target)

299 
for i in range(count): 
300 
yield list(visited) + [target] 
301 
stack.pop() 
302 
visited.popitem() 
303  
304  
305 
@not_implemented_for('multigraph') 
306 
def shortest_simple_paths(G, source, target, weight=None): 
307 
"""Generate all simple paths in the graph G from source to target,

308 
starting from shortest ones.

309 

310 
A simple path is a path with no repeated nodes.

311 

312 
If a weighted shortest path search is to be used, no negative weights

313 
are allowed.

314 

315 
Parameters

316 


317 
G : NetworkX graph

318 

319 
source : node

320 
Starting node for path

321 

322 
target : node

323 
Ending node for path

324 

325 
weight : string

326 
Name of the edge attribute to be used as a weight. If None all

327 
edges are considered to have unit weight. Default value None.

328 

329 
Returns

330 


331 
path_generator: generator

332 
A generator that produces lists of simple paths, in order from

333 
shortest to longest.

334 

335 
Raises

336 


337 
NetworkXNoPath

338 
If no path exists between source and target.

339 

340 
NetworkXError

341 
If source or target nodes are not in the input graph.

342 

343 
NetworkXNotImplemented

344 
If the input graph is a Multi[Di]Graph.

345 

346 
Examples

347 


348 

349 
>>> G = nx.cycle_graph(7)

350 
>>> paths = list(nx.shortest_simple_paths(G, 0, 3))

351 
>>> print(paths)

352 
[[0, 1, 2, 3], [0, 6, 5, 4, 3]]

353 

354 
You can use this function to efficiently compute the k shortest/best

355 
paths between two nodes.

356 

357 
>>> from itertools import islice

358 
>>> def k_shortest_paths(G, source, target, k, weight=None):

359 
... return list(islice(nx.shortest_simple_paths(G, source, target, weight=weight), k))

360 
>>> for path in k_shortest_paths(G, 0, 3, 2):

361 
... print(path)

362 
[0, 1, 2, 3]

363 
[0, 6, 5, 4, 3]

364 

365 
Notes

366 


367 
This procedure is based on algorithm by Jin Y. Yen [1]_. Finding

368 
the first $K$ paths requires $O(KN^3)$ operations.

369 

370 
See Also

371 


372 
all_shortest_paths

373 
shortest_path

374 
all_simple_paths

375 

376 
References

377 


378 
.. [1] Jin Y. Yen, "Finding the K Shortest Loopless Paths in a

379 
Network", Management Science, Vol. 17, No. 11, Theory Series

380 
(Jul., 1971), pp. 712716.

381 

382 
"""

383 
if source not in G: 
384 
raise nx.NodeNotFound('source node %s not in graph' % source) 
385  
386 
if target not in G: 
387 
raise nx.NodeNotFound('target node %s not in graph' % target) 
388  
389 
if weight is None: 
390 
length_func = len

391 
shortest_path_func = _bidirectional_shortest_path 
392 
else:

393 
def length_func(path): 
394 
return sum(G.adj[u][v][weight] for (u, v) in zip(path, path[1:])) 
395 
shortest_path_func = _bidirectional_dijkstra 
396  
397 
listA = list()

398 
listB = PathBuffer() 
399 
prev_path = None

400 
while True: 
401 
if not prev_path: 
402 
length, path = shortest_path_func(G, source, target, weight=weight) 
403 
listB.push(length, path) 
404 
else:

405 
ignore_nodes = set()

406 
ignore_edges = set()

407 
for i in range(1, len(prev_path)): 
408 
root = prev_path[:i] 
409 
root_length = length_func(root) 
410 
for path in listA: 
411 
if path[:i] == root:

412 
ignore_edges.add((path[i  1], path[i]))

413 
try:

414 
length, spur = shortest_path_func(G, root[1], target,

415 
ignore_nodes=ignore_nodes, 
416 
ignore_edges=ignore_edges, 
417 
weight=weight) 
418 
path = root[:1] + spur

419 
listB.push(root_length + length, path) 
420 
except nx.NetworkXNoPath:

421 
pass

422 
ignore_nodes.add(root[1])

423  
424 
if listB:

425 
path = listB.pop() 
426 
yield path

427 
listA.append(path) 
428 
prev_path = path 
429 
else:

430 
break

431  
432  
433 
class PathBuffer(object): 
434  
435 
def __init__(self): 
436 
self.paths = set() 
437 
self.sortedpaths = list() 
438 
self.counter = count()

439  
440 
def __len__(self): 
441 
return len(self.sortedpaths) 
442  
443 
def push(self, cost, path): 
444 
hashable_path = tuple(path)

445 
if hashable_path not in self.paths: 
446 
heappush(self.sortedpaths, (cost, next(self.counter), path)) 
447 
self.paths.add(hashable_path)

448  
449 
def pop(self): 
450 
(cost, num, path) = heappop(self.sortedpaths)

451 
hashable_path = tuple(path)

452 
self.paths.remove(hashable_path)

453 
return path

454  
455  
456 
def _bidirectional_shortest_path(G, source, target, 
457 
ignore_nodes=None,

458 
ignore_edges=None,

459 
weight=None):

460 
"""Returns the shortest path between source and target ignoring

461 
nodes and edges in the containers ignore_nodes and ignore_edges.

462 

463 
This is a custom modification of the standard bidirectional shortest

464 
path implementation at networkx.algorithms.unweighted

465 

466 
Parameters

467 


468 
G : NetworkX graph

469 

470 
source : node

471 
starting node for path

472 

473 
target : node

474 
ending node for path

475 

476 
ignore_nodes : container of nodes

477 
nodes to ignore, optional

478 

479 
ignore_edges : container of edges

480 
edges to ignore, optional

481 

482 
weight : None

483 
This function accepts a weight argument for convenience of

484 
shortest_simple_paths function. It will be ignored.

485 

486 
Returns

487 


488 
path: list

489 
List of nodes in a path from source to target.

490 

491 
Raises

492 


493 
NetworkXNoPath

494 
If no path exists between source and target.

495 

496 
See Also

497 


498 
shortest_path

499 

500 
"""

501 
# call helper to do the real work

502 
results = _bidirectional_pred_succ(G, source, target, ignore_nodes, ignore_edges) 
503 
pred, succ, w = results 
504  
505 
# build path from pred+w+succ

506 
path = [] 
507 
# from w to target

508 
while w is not None: 
509 
path.append(w) 
510 
w = succ[w] 
511 
# from source to w

512 
w = pred[path[0]]

513 
while w is not None: 
514 
path.insert(0, w)

515 
w = pred[w] 
516  
517 
return len(path), path 
518  
519  
520 
def _bidirectional_pred_succ(G, source, target, ignore_nodes=None, ignore_edges=None): 
521 
"""Bidirectional shortest path helper.

522 
Returns (pred,succ,w) where

523 
pred is a dictionary of predecessors from w to the source, and

524 
succ is a dictionary of successors from w to the target.

525 
"""

526 
# does BFS from both source and target and meets in the middle

527 
if ignore_nodes and (source in ignore_nodes or target in ignore_nodes): 
528 
raise nx.NetworkXNoPath("No path between %s and %s." % (source, target)) 
529 
if target == source:

530 
return ({target: None}, {source: None}, source) 
531  
532 
# handle either directed or undirected

533 
if G.is_directed():

534 
Gpred = G.predecessors 
535 
Gsucc = G.successors 
536 
else:

537 
Gpred = G.neighbors 
538 
Gsucc = G.neighbors 
539  
540 
# support optional nodes filter

541 
if ignore_nodes:

542 
def filter_iter(nodes): 
543 
def iterate(v): 
544 
for w in nodes(v): 
545 
if w not in ignore_nodes: 
546 
yield w

547 
return iterate

548  
549 
Gpred = filter_iter(Gpred) 
550 
Gsucc = filter_iter(Gsucc) 
551  
552 
# support optional edges filter

553 
if ignore_edges:

554 
if G.is_directed():

555 
def filter_pred_iter(pred_iter): 
556 
def iterate(v): 
557 
for w in pred_iter(v): 
558 
if (w, v) not in ignore_edges: 
559 
yield w

560 
return iterate

561  
562 
def filter_succ_iter(succ_iter): 
563 
def iterate(v): 
564 
for w in succ_iter(v): 
565 
if (v, w) not in ignore_edges: 
566 
yield w

567 
return iterate

568  
569 
Gpred = filter_pred_iter(Gpred) 
570 
Gsucc = filter_succ_iter(Gsucc) 
571  
572 
else:

573 
def filter_iter(nodes): 
574 
def iterate(v): 
575 
for w in nodes(v): 
576 
if (v, w) not in ignore_edges \ 
577 
and (w, v) not in ignore_edges: 
578 
yield w

579 
return iterate

580  
581 
Gpred = filter_iter(Gpred) 
582 
Gsucc = filter_iter(Gsucc) 
583  
584 
# predecesssor and successors in search

585 
pred = {source: None}

586 
succ = {target: None}

587  
588 
# initialize fringes, start with forward

589 
forward_fringe = [source] 
590 
reverse_fringe = [target] 
591  
592 
while forward_fringe and reverse_fringe: 
593 
if len(forward_fringe) <= len(reverse_fringe): 
594 
this_level = forward_fringe 
595 
forward_fringe = [] 
596 
for v in this_level: 
597 
for w in Gsucc(v): 
598 
if w not in pred: 
599 
forward_fringe.append(w) 
600 
pred[w] = v 
601 
if w in succ: 
602 
# found path

603 
return pred, succ, w

604 
else:

605 
this_level = reverse_fringe 
606 
reverse_fringe = [] 
607 
for v in this_level: 
608 
for w in Gpred(v): 
609 
if w not in succ: 
610 
succ[w] = v 
611 
reverse_fringe.append(w) 
612 
if w in pred: 
613 
# found path

614 
return pred, succ, w

615  
616 
raise nx.NetworkXNoPath("No path between %s and %s." % (source, target)) 
617  
618  
619 
def _bidirectional_dijkstra(G, source, target, weight='weight', 
620 
ignore_nodes=None, ignore_edges=None): 
621 
"""Dijkstra's algorithm for shortest paths using bidirectional search.

622 

623 
This function returns the shortest path between source and target

624 
ignoring nodes and edges in the containers ignore_nodes and

625 
ignore_edges.

626 

627 
This is a custom modification of the standard Dijkstra bidirectional

628 
shortest path implementation at networkx.algorithms.weighted

629 

630 
Parameters

631 


632 
G : NetworkX graph

633 

634 
source : node

635 
Starting node.

636 

637 
target : node

638 
Ending node.

639 

640 
weight: string, optional (default='weight')

641 
Edge data key corresponding to the edge weight

642 

643 
ignore_nodes : container of nodes

644 
nodes to ignore, optional

645 

646 
ignore_edges : container of edges

647 
edges to ignore, optional

648 

649 
Returns

650 


651 
length : number

652 
Shortest path length.

653 

654 
Returns a tuple of two dictionaries keyed by node.

655 
The first dictionary stores distance from the source.

656 
The second stores the path from the source to that node.

657 

658 
Raises

659 


660 
NetworkXNoPath

661 
If no path exists between source and target.

662 

663 
Notes

664 


665 
Edge weight attributes must be numerical.

666 
Distances are calculated as sums of weighted edges traversed.

667 

668 
In practice bidirectional Dijkstra is much more than twice as fast as

669 
ordinary Dijkstra.

670 

671 
Ordinary Dijkstra expands nodes in a spherelike manner from the

672 
source. The radius of this sphere will eventually be the length

673 
of the shortest path. Bidirectional Dijkstra will expand nodes

674 
from both the source and the target, making two spheres of half

675 
this radius. Volume of the first sphere is pi*r*r while the

676 
others are 2*pi*r/2*r/2, making up half the volume.

677 

678 
This algorithm is not guaranteed to work if edge weights

679 
are negative or are floating point numbers

680 
(overflows and roundoff errors can cause problems).

681 

682 
See Also

683 


684 
shortest_path

685 
shortest_path_length

686 
"""

687 
if ignore_nodes and (source in ignore_nodes or target in ignore_nodes): 
688 
raise nx.NetworkXNoPath("No path between %s and %s." % (source, target)) 
689 
if source == target:

690 
return (0, [source]) 
691  
692 
# handle either directed or undirected

693 
if G.is_directed():

694 
Gpred = G.predecessors 
695 
Gsucc = G.successors 
696 
else:

697 
Gpred = G.neighbors 
698 
Gsucc = G.neighbors 
699  
700 
# support optional nodes filter

701 
if ignore_nodes:

702 
def filter_iter(nodes): 
703 
def iterate(v): 
704 
for w in nodes(v): 
705 
if w not in ignore_nodes: 
706 
yield w

707 
return iterate

708  
709 
Gpred = filter_iter(Gpred) 
710 
Gsucc = filter_iter(Gsucc) 
711  
712 
# support optional edges filter

713 
if ignore_edges:

714 
if G.is_directed():

715 
def filter_pred_iter(pred_iter): 
716 
def iterate(v): 
717 
for w in pred_iter(v): 
718 
if (w, v) not in ignore_edges: 
719 
yield w

720 
return iterate

721  
722 
def filter_succ_iter(succ_iter): 
723 
def iterate(v): 
724 
for w in succ_iter(v): 
725 
if (v, w) not in ignore_edges: 
726 
yield w

727 
return iterate

728  
729 
Gpred = filter_pred_iter(Gpred) 
730 
Gsucc = filter_succ_iter(Gsucc) 
731  
732 
else:

733 
def filter_iter(nodes): 
734 
def iterate(v): 
735 
for w in nodes(v): 
736 
if (v, w) not in ignore_edges \ 
737 
and (w, v) not in ignore_edges: 
738 
yield w

739 
return iterate

740  
741 
Gpred = filter_iter(Gpred) 
742 
Gsucc = filter_iter(Gsucc) 
743  
744 
push = heappush 
745 
pop = heappop 
746 
# Init: Forward Backward

747 
dists = [{}, {}] # dictionary of final distances

748 
paths = [{source: [source]}, {target: [target]}] # dictionary of paths

749 
fringe = [[], []] # heap of (distance, node) tuples for

750 
# extracting next node to expand

751 
seen = [{source: 0}, {target: 0}] # dictionary of distances to 
752 
# nodes seen

753 
c = count() 
754 
# initialize fringe heap

755 
push(fringe[0], (0, next(c), source)) 
756 
push(fringe[1], (0, next(c), target)) 
757 
# neighs for extracting correct neighbor information

758 
neighs = [Gsucc, Gpred] 
759 
# variables to hold shortest discovered path

760 
#finaldist = 1e30000

761 
finalpath = [] 
762 
dir = 1

763 
while fringe[0] and fringe[1]: 
764 
# choose direction

765 
# dir == 0 is forward direction and dir == 1 is back

766 
dir = 1  dir 
767 
# extract closest to expand

768 
(dist, _, v) = pop(fringe[dir])

769 
if v in dists[dir]: 
770 
# Shortest path to v has already been found

771 
continue

772 
# update distance

773 
dists[dir][v] = dist # equal to seen[dir][v] 
774 
if v in dists[1  dir]: 
775 
# if we have scanned v in both directions we are done

776 
# we have now discovered the shortest path

777 
return (finaldist, finalpath)

778  
779 
for w in neighs[dir](v): 
780 
if(dir == 0): # forward 
781 
if G.is_multigraph():

782 
minweight = min((dd.get(weight, 1) 
783 
for k, dd in G[v][w].items())) 
784 
else:

785 
minweight = G[v][w].get(weight, 1)

786 
vwLength = dists[dir][v] + minweight # G[v][w].get(weight,1) 
787 
else: # back, must remember to change v,w>w,v 
788 
if G.is_multigraph():

789 
minweight = min((dd.get(weight, 1) 
790 
for k, dd in G[w][v].items())) 
791 
else:

792 
minweight = G[w][v].get(weight, 1)

793 
vwLength = dists[dir][v] + minweight # G[w][v].get(weight,1) 
794  
795 
if w in dists[dir]: 
796 
if vwLength < dists[dir][w]: 
797 
raise ValueError( 
798 
"Contradictory paths found: negative weights?")

799 
elif w not in seen[dir] or vwLength < seen[dir][w]: 
800 
# relaxing

801 
seen[dir][w] = vwLength

802 
push(fringe[dir], (vwLength, next(c), w)) 
803 
paths[dir][w] = paths[dir][v] + [w] 
804 
if w in seen[0] and w in seen[1]: 
805 
# see if this path is better than than the already

806 
# discovered shortest path

807 
totaldist = seen[0][w] + seen[1][w] 
808 
if finalpath == [] or finaldist > totaldist: 
809 
finaldist = totaldist 
810 
revpath = paths[1][w][:]

811 
revpath.reverse() 
812 
finalpath = paths[0][w] + revpath[1:] 
813 
raise nx.NetworkXNoPath("No path between %s and %s." % (source, target)) 