« back to all changes in this revision
Viewing changes to bzrlib/graph.py
- browse files at revision 974.1.65
- compare with another revision
- compare with revision 1110
- download diff
- download tarball
- view history from revision 974.1.65
- Committer: Aaron Bentley
- Date: 2005-09-10 23:15:33 UTC
- mto: (1185.3.4)
- mto: This revision was merged to the branch mainline in revision 1390.
- Revision ID: aaron.bentley@utoronto.ca-20050910231533-e3860a46890c2c71
Cleanup and test-fixing
added
removed
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]
123
124
def farthest_nodes_ab(graph, start):
125
lines = [start]
126
predecessors = {}
127
endpoints = {}
128
while len(lines) > 0:
129
new_lines = set()
130
for line in lines:
131
for child in graph[line]:
132
if child not in predecessors:
133
new_lines.add(child)
134
predecessors[child] = line
135
else:
136
endpoints[line] = None
137
lines = new_lines
138
distances = []
139
for endpoint in endpoints:
140
path = []
141
node = endpoint
142
while node != start:
143
path.append(node)
144
node = predecessors[node]
145
distances.append((len(path), endpoint))
146
distances.sort(reverse=True)
147
return [d[1] for d in distances]
148
149
1
150
2
def max_distance(node, ancestors, distances):
151
3
"""Calculate the max distance to an ancestor. Return None if"""
152
4
best = None
154
6
best = distances[node]
155
7
for ancestor in ancestors[node]:
156
8
if ancestor not in ancestors:
157
print ancestor
158
9
continue
159
10
if ancestor not in distances:
160
11
return None
164
15
165
16
166
17
def farthest_node(graph, ancestors, start):
167
assert 'A' in graph
168
18
distances = {start: 0}
169
19
lines = set([start])
170
20
while len(lines) > 0:
Loggerhead is a web-based interface for Breezy
Version: 2.0.1