~bzr-pqm/bzr/1.17

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

merge merge tweaks from aaron, which includes latest .dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
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: