← 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-12 02:53:07 UTC
  • mto: (1185.3.4)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: aaron.bentley@utoronto.ca-20050912025307-8c21544e8db1cbdb
added all_descendants and node_distances, exception when root doesn't exist

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
 
def max_distance(node, ancestors, distances):
 
17
def max_distance(node, ancestors, distances, root_descendants):
18
18
    """Calculate the max distance to an ancestor.  
19
19
    Return None if not all possible ancestors have known distances"""
20
20
    best = None
21
21
    if node in distances:
22
22
        best = distances[node]
23
23
    for ancestor in ancestors[node]:
 
24
        # skip ancestors we will never traverse:
 
25
        if root_descendants is not None and ancestor not in root_descendants:
 
26
            continue
24
27
        # An ancestor which is not listed in ancestors will never be in
25
28
        # distances, so we pretend it never existed.
26
29
        if ancestor not in ancestors:
32
35
    return best
33
36
 
34
37
    
35
 
def farthest_nodes(graph, ancestors, start):
 
38
def node_distances(graph, ancestors, start, root_descendants=None):
36
39
    """Produce a list of nodes, sorted by distance from a start node.
37
40
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
38
41
    backwards seemed too complicated.
52
55
    while len(lines) > 0:
53
56
        new_lines = set()
54
57
        for line in lines:
55
 
            assert line not in graph[line], "%s refers to itself" % line
56
 
            for descendant in graph[line]:
57
 
                distance = max_distance(descendant, ancestors, distances)
 
58
            line_descendants = graph[line]
 
59
            assert line not in line_descendants, "%s refers to itself" % line
 
60
            for descendant in line_descendants:
 
61
                distance = max_distance(descendant, ancestors, distances,
 
62
                                        root_descendants)
58
63
                if distance is None:
59
64
                    continue
60
65
                distances[descendant] = distance
61
66
                new_lines.add(descendant)
62
67
        lines = new_lines
 
68
    return distances
63
69
 
 
70
def farthest_nodes(graph, ancestors, start):
64
71
    def by_distance(n):
65
72
        return distances[n],n
 
73
 
 
74
    distances = node_distances(graph, ancestors, start)
66
75
    node_list = distances.keys()
67
76
    node_list.sort(key=by_distance, reverse=True)
68
77
    return node_list
 
78
 
 
79
def all_descendants(descendants, start):
 
80
    result = set()
 
81
    lines = set([start])
 
82
    while len(lines) > 0:
 
83
        new_lines = set()
 
84
        for line in lines:
 
85
            if line not in descendants:
 
86
                continue
 
87
            for descendant in descendants[line]:
 
88
                if descendant in result:
 
89
                    continue
 
90
                result.add(descendant)
 
91
                new_lines.add(descendant)
 
92
        lines = new_lines
 
93
    return result