← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: aaron.bentley at utoronto
  • Date: 2005-09-05 07:11:41 UTC
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050905071141-5f9ef30b0f6b3e21
Started work on djkstra longest-path algorithm

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
 
1
# Dijkstra's algorithm for shortest paths
 
2
# David Eppstein, UC Irvine, 4 April 2002
 
3
 
 
4
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
 
5
from priodict import priorityDictionary
 
6
 
 
7
def dijkstra(G,start,end=None):
 
8
        """
 
9
        Find shortest paths from the start vertex to all
 
10
        vertices nearer than or equal to the end.
 
11
 
 
12
        The input graph G is assumed to have the following
 
13
        representation: A vertex can be any object that can
 
14
        be used as an index into a dictionary.  G is a
 
15
        dictionary, indexed by vertices.  For any vertex v,
 
16
        G[v] is itself a dictionary, indexed by the neighbors
 
17
        of v.  For any edge v->w, G[v][w] is the length of
 
18
        the edge.  This is related to the representation in
 
19
        <http://www.python.org/doc/essays/graphs.html>
 
20
        where Guido van Rossum suggests representing graphs
 
21
        as dictionaries mapping vertices to lists of neighbors,
 
22
        however dictionaries of edges have many advantages
 
23
        over lists: they can store extra information (here,
 
24
        the lengths), they support fast existence tests,
 
25
        and they allow easy modification of the graph by edge
 
26
        insertion and removal.  Such modifications are not
 
27
        needed here but are important in other graph algorithms.
 
28
        Since dictionaries obey iterator protocol, a graph
 
29
        represented as described here could be handed without
 
30
        modification to an algorithm using Guido's representation.
 
31
 
 
32
        Of course, G and G[v] need not be Python dict objects;
 
33
        they can be any other object that obeys dict protocol,
 
34
        for instance a wrapper in which vertices are URLs
 
35
        and a call to G[v] loads the web page and finds its links.
 
36
        
 
37
        The output is a pair (D,P) where D[v] is the distance
 
38
        from start to v and P[v] is the predecessor of v along
 
39
        the shortest path from s to v.
 
40
        
 
41
        Dijkstra's algorithm is only guaranteed to work correctly
 
42
        when all edge lengths are positive. This code does not
 
43
        verify this property for all edges (only the edges seen
 
44
        before the end vertex is reached), but will correctly
 
45
        compute shortest paths even for some graphs with negative
 
46
        edges, and will raise an exception if it discovers that
 
47
        a negative edge has caused it to make a mistake.
 
48
        """
 
49
 
 
50
        D = {}  # dictionary of final distances
 
51
        P = {}  # dictionary of predecessors
 
52
        Q = priorityDictionary()  # est.dist. of non-final vert.
 
53
        Q[start] = 0
 
54
        
 
55
        for v in Q:
 
56
                D[v] = Q[v]
 
57
                if v == end: break
 
58
                
 
59
                for w in G[v]:
 
60
                        vwLength = D[v] + G[v][w]
 
61
                        if w in D:
 
62
                                if vwLength < D[w]:
 
63
                                        raise ValueError, \
 
64
  "Dijkstra: found better path to already-final vertex"
 
65
                        elif w not in Q or vwLength < Q[w]:
 
66
                                Q[w] = vwLength
 
67
                                P[w] = v
 
68
        
 
69
        return (D,P)
 
70
                        
 
71
def shortest_path(G,start, end):
 
72
        """
 
73
        Find a single shortest path from the given start vertex
 
74
        to the given end vertex.
 
75
        The input has the same conventions as Dijkstra().
 
76
        The output is a list of the vertices in order along
 
77
        the shortest path.
 
78
        """
 
79
 
 
80
        D,P = dijkstra(G,start,end)
 
81
        print D,P
 
82
        Path = []
 
83
        while 1:
 
84
                Path.append(end)
 
85
                if end == start: break
 
86
                end = P[end]
 
87
        Path.reverse()
 
88
        return Path
 
89
 
 
90
def closest(distances, pending):
 
91
    closest = None
 
92
    for node in pending:
 
93
        distance = distances[node]
 
94
        if distance is None:
 
95
            continue
 
96
        if closest is None or distance < closest[1]:
 
97
            closest = (node, distance)
 
98
    return closest[0] 
 
99
 
 
100
def relax(node, distances, graph):
 
101
    for child in graph[node]:
 
102
        new_distance = distances[node] + graph[node][child]
 
103
        if distances[child] is None or distances[child] < new_distance:
 
104
            print "setting %s to %d, from %s(%d)" % (child, new_distance, node,
 
105
            distances[node])
 
106
            distances[child] = new_distance
 
107
 
 
108
def farthest_node(graph, start):
 
109
    done = set()
 
110
    distances = {}
 
111
    pending = set(graph.keys())
 
112
    for node in graph:
 
113
        distances[node] = None
 
114
    distances[start] = 0
 
115
    while len(done) < len(distances):
 
116
        node = closest(distances, pending)
 
117
        done.add(node)
 
118
        pending.remove(node)
 
119
        relax(node, distances, graph)
 
120
    print distances
 
121
    distfirst = [(d, n) for n, d in distances.iteritems()]
 
122
    return distfirst[-1][1]