2
def max_distance(node, ancestors, distances):
3
"""Calculate the max distance to an ancestor.
4
Return None if not all possible ancestors have known distances"""
8
for ancestor in ancestors[node]:
9
# An ancestor which is not listed in ancestors will never be in
10
# distances, so we pretend it never existed.
11
if ancestor not in ancestors:
13
if ancestor not in distances:
15
if best is None or distances[ancestor] > best:
16
best = distances[ancestor] + 1
20
def farthest_nodes(graph, ancestors, start):
21
"""Produce a list of nodes, sorted by distance from a start node.
22
This is an algorithm devised by Aaron Bentley, because applying Dijkstra
23
backwards seemed too complicated.
25
For each node, we walk its descendants. If all the descendant's ancestors
26
have a max-distance-to-start, (excluding ones that can never reach start),
27
we calculate their max-distance-to-start, and schedule their descendants.
29
So when a node's last parent acquires a distance, it will acquire a
30
distance on the next iteration.
32
Once we know the max distances for all nodes, we can return a list sorted
33
by distance, farthest first.
35
distances = {start: 0}
40
assert line not in graph[line], "%s refers to itself" % line
41
for descendant in graph[line]:
42
distance = max_distance(descendant, ancestors, distances)
45
distances[descendant] = distance
46
new_lines.add(descendant)
51
node_list = distances.keys()
52
node_list.sort(key=by_distance, reverse=True)
added
removed
bzrlib/graph.py
