← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Martin Pool
  • Date: 2005-10-06 10:53:12 UTC
  • mto: (1185.13.3)
  • mto: This revision was merged to the branch mainline in revision 1418.
  • Revision ID: mbp@sourcefrog.net-20051006105312-06320dbb986e4bb3
- test that we cannot join weaves with different ancestry

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
30
30
            continue
31
31
        if ancestor not in distances:
32
32
            return None
33
 
        if best is None or distances[ancestor] > best:
 
33
        if best is None or distances[ancestor]+1 > best:
34
34
            best = distances[ancestor] + 1
35
35
    return best
36
36
 
67
67
        lines = new_lines
68
68
    return distances
69
69
 
70
 
def farthest_nodes(graph, ancestors, start):
 
70
def nodes_by_distance(distances):
 
71
    """Return a list of nodes sorted by distance"""
71
72
    def by_distance(n):
72
73
        return distances[n],n
73
74
 
74
 
    distances = node_distances(graph, ancestors, start)
75
75
    node_list = distances.keys()
76
76
    node_list.sort(key=by_distance, reverse=True)
77
77
    return node_list
78
78
 
 
79
def select_farthest(distances, common):
 
80
    """Return the farthest common node, or None if no node qualifies."""
 
81
    node_list = nodes_by_distance(distances)
 
82
    for node in node_list:
 
83
        if node in common:
 
84
            return node
 
85
 
79
86
def all_descendants(descendants, start):
 
87
    """Produce a set of all descendants of the start node.
 
88
    The input is a map of node->list of descendants for a graph encompassing
 
89
    start.
 
90
    """
80
91
    result = set()
81
92
    lines = set([start])
82
93
    while len(lines) > 0: