← 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
  • Date: 2005-09-18 19:21:48 UTC
  • mto: (1185.1.29)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050918192148-3f9373ac85a83b02
Refactored and documented graph stuff

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
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: