← 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
  • Date: 2005-09-10 23:37:36 UTC
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050910233735-0cc3a7a2617bc79c
more cleanups, docs, sorting stuff

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
1
        
2
2
def max_distance(node, ancestors, distances):
3
 
    """Calculate the max distance to an ancestor.  Return None if"""
 
3
    """Calculate the max distance to an ancestor.  
 
4
    Return None if not all possible ancestors have known distances"""
4
5
    best = None
5
6
    if node in distances:
6
7
        best = distances[node]
7
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.
8
11
        if ancestor not in ancestors:
9
12
            continue
10
13
        if ancestor not in distances:
14
17
    return best
15
18
 
16
19
    
17
 
def farthest_node(graph, ancestors, start):
 
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.
 
24
 
 
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.
 
28
 
 
29
    So when a node's last parent acquires a distance, it will acquire a
 
30
    distance on the next iteration.
 
31
 
 
32
    Once we know the max distances for all nodes, we can return a list sorted
 
33
    by distance, farthest first.
 
34
    """
18
35
    distances = {start: 0}
19
36
    lines = set([start])
20
37
    while len(lines) > 0:
30
47
        lines = new_lines
31
48
 
32
49
    def by_distance(n):
33
 
        return distances[n]
 
50
        return distances[n],n
34
51
    node_list = distances.keys()
35
52
    node_list.sort(key=by_distance, reverse=True)
36
53
    return node_list