← 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-06 04:14:01 UTC
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050906041400-0c6374f33ab472d3
Created yet another longest-patch-picker

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
145
145
        distances.append((len(path), endpoint))
146
146
    distances.sort(reverse=True)
147
147
    return [d[1] for d in distances]
 
148
 
 
149
 
 
150
def max_distance(node, ancestors, distances):
 
151
    """Calculate the max distance to an ancestor.  Return None if"""
 
152
    best = None
 
153
    if node in distances:
 
154
        best = distances[node]
 
155
    for ancestor in ancestors[node]:
 
156
        if ancestor not in distances:
 
157
            return None
 
158
        if best is None or distances[ancestor] > best:
 
159
            best = distances[ancestor] + 1
 
160
    return best
 
161
 
 
162
    
 
163
def farthest_node(graph, ancestors, start):
 
164
    distances = {start: 0}
 
165
    lines = set(start)
 
166
    while len(lines) > 0:
 
167
        new_lines = set()
 
168
        for line in lines:
 
169
            for descendant in graph[line]:
 
170
                distance = max_distance(descendant, ancestors, distances)
 
171
                if distance is None:
 
172
                    continue
 
173
                distances[descendant] = distance
 
174
                new_lines.add(descendant)
 
175
        lines = new_lines
 
176
 
 
177
    def by_distance(n):
 
178
        return distances[n]
 
179
    node_list = distances.keys()
 
180
    node_list.sort(key=by_distance, reverse=True)
 
181
    return node_list