Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / simple_paths.py @ 5cef0f13

History | View | Annotate | Download (25.5 KB)

1
# -*- coding: utf-8 -*-
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 depth-first 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. 712-716.
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 sphere-like 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))