← 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-05 20:22:32 UTC
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050905202231-3c83cce239fdf4c6
Implemented yet another farthest_node algorithm

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
120
120
    print distances
121
121
    distfirst = [(d, n) for n, d in distances.iteritems()]
122
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]