← Back to branch summary

~abentley/bzrtools/bzrtools.dev

« back to all changes in this revision

Viewing changes to graph.py

  • Committer: Aaron Bentley
  • Date: 2011-09-25 01:18:55 UTC
  • mfrom: (776.2.1 unused-imports)
  • Revision ID: aaron@aaronbentley.com-20110925011855-3dil4ijgluvzq7q5
Remove unused imports, fix the importing of two error classes. (jelmer)

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
20
20
 
21
21
from bzrlib.branch import Branch
22
22
from bzrlib.errors import BzrCommandError, NoSuchRevision
23
 
from bzrlib.graph import node_distances, select_farthest
24
23
from bzrlib.revision import NULL_REVISION
25
24
 
26
25
from bzrtools import short_committer
38
37
    )
39
38
 
40
39
 
 
40
def max_distance(node, ancestors, distances, root_descendants):
 
41
    """Calculate the max distance to an ancestor.
 
42
    Return None if not all possible ancestors have known distances"""
 
43
    best = None
 
44
    if node in distances:
 
45
        best = distances[node]
 
46
    for ancestor in ancestors[node]:
 
47
        # skip ancestors we will never traverse:
 
48
        if root_descendants is not None and ancestor not in root_descendants:
 
49
            continue
 
50
        # An ancestor which is not listed in ancestors will never be in
 
51
        # distances, so we pretend it never existed.
 
52
        if ancestor not in ancestors:
 
53
            continue
 
54
        if ancestor not in distances:
 
55
            return None
 
56
        if best is None or distances[ancestor]+1 > best:
 
57
            best = distances[ancestor] + 1
 
58
    return best
 
59
 
 
60
 
 
61
def node_distances(graph, ancestors, start, root_descendants=None):
 
62
    """Produce a list of nodes, sorted by distance from a start node.
 
63
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
 
64
    backwards seemed too complicated.
 
65
 
 
66
    For each node, we walk its descendants.  If all the descendant's ancestors
 
67
    have a max-distance-to-start, (excluding ones that can never reach start),
 
68
    we calculate their max-distance-to-start, and schedule their descendants.
 
69
 
 
70
    So when a node's last parent acquires a distance, it will acquire a
 
71
    distance on the next iteration.
 
72
 
 
73
    Once we know the max distances for all nodes, we can return a list sorted
 
74
    by distance, farthest first.
 
75
    """
 
76
    distances = {start: 0}
 
77
    lines = set([start])
 
78
    while len(lines) > 0:
 
79
        new_lines = set()
 
80
        for line in lines:
 
81
            line_descendants = graph[line]
 
82
            for descendant in line_descendants:
 
83
                distance = max_distance(descendant, ancestors, distances,
 
84
                                        root_descendants)
 
85
                if distance is None:
 
86
                    continue
 
87
                distances[descendant] = distance
 
88
                new_lines.add(descendant)
 
89
        lines = new_lines
 
90
    return distances
 
91
 
 
92
 
 
93
def nodes_by_distance(distances):
 
94
    """Return a list of nodes sorted by distance"""
 
95
    def by_distance(n):
 
96
        return distances[n],n
 
97
 
 
98
    node_list = distances.keys()
 
99
    node_list.sort(key=by_distance, reverse=True)
 
100
    return node_list
 
101
 
 
102
 
 
103
def select_farthest(distances, common):
 
104
    """Return the farthest common node, or None if no node qualifies."""
 
105
    node_list = nodes_by_distance(distances)
 
106
    for node in node_list:
 
107
        if node in common:
 
108
            return node
 
109
 
 
110
 
41
111
mail_map = {'aaron.bentley@utoronto.ca'     : 'Aaron Bentley',
42
112
            'abentley@panoramicfeedback.com': 'Aaron Bentley',
43
113
            'abentley@lappy'                : 'Aaron Bentley',