Dissertation-Network-Analysis/path.py at master · Flaminis/Dissertation-Network-Analysis · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from mygraph import MyGraph
from heapq import heappush, heappop
from itertools import count
import networkx as nx
def bidirectional_dijkstra(G, source, target, needpath, weight='weight'):
    # efficent shortest path
    if source == target:
        if needpath:
            return 0
        else:
            return (0, [source])
    hpush = heappush
    hpop = heappop
    # Init:   Forward             Backward
    distances  = [{},{}]  # dictionary of final distances
    paths  = [{source: [source]}, {target: [target]}]  # dictionary of paths
    fringe = [[],[]]  # heap of (distance, node) tuples for
                      # extracting next node to expand
    seen   = [{source: 0},{target: 0}]  # dictionary of distances to
                                                # nodes seen
    c = count()
    # initialize fringe heap
    hpush(fringe[0], (0, next(c), source))
    hpush(fringe[1], (0, next(c), target))
    # neighs for extracting correct neighbor information

    neighs = [G.nbrs_iterator, G.nbrs_iterator]
    # variables to hold shortest discovered path
    #finaldist = 1e30000
    finalpath = []
    dir = 1
    while fringe[0] and fringe[1]:
        # choose direction
        # dir == 0 is forward direction and dir == 1 is back
        dir = 1 - dir
        # extract closest to expand
        (dist, _, v) = hpop(fringe[dir])
        if v in distances[dir]:
            # Shortest path to v has already been found
            continue
        # update distance
        distances[dir][v] = dist  # equal to seen[dir][v]
        if v in distances[1 - dir]:
            # if we have scanned v in both directions we are done
            # we have now discovered the shortest path
            if needpath:
                return (finaldist, finalpath)
            else:
                return finaldist
        for w in neighs[dir](v):
            if(dir == 0):  # forward
                minweight = G[v][w]['weight']
                vwLength = distances[dir][v] + minweight  # G[v][w].get(weight,1)
            else:  # back, must remember to change v,w->w,v
                minweight = G[w][v].get(weight, 1)
                vwLength = distances[dir][v] + minweight  # G[w][v].get(weight,1)

            if w in distances[dir]:
                if vwLength < distances[dir][w]:
                    raise ValueError(
                        "Contradictory paths found: negative weights?")
            elif w not in seen[dir] or vwLength < seen[dir][w]:
                # relaxing
                seen[dir][w] = vwLength
                hpush(fringe[dir], (vwLength, next(c), w))
                paths[dir][w] = paths[dir][v] + [w]
                if w in seen[0] and w in seen[1]:
                    # see if this path is better than than the already
                    # discovered shortest path
                    totaldist = seen[0][w] + seen[1][w]
                    if finalpath == [] or finaldist > totaldist:
                        finaldist = totaldist
                        revpath = paths[1][w][:]
                        revpath.reverse()
                        finalpath = paths[0][w] + revpath[1:]
    return 100000