← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Lalo Martins
  • Date: 2005-09-09 10:58:51 UTC
  • mto: (1185.1.22)
  • mto: This revision was merged to the branch mainline in revision 1390.
  • Revision ID: lalo@exoweb.net-20050909105851-25aa36ea27f4ce7b
creating the new branch constructors

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# (C) 2005 Canonical
2
 
 
3
 
# This program is free software; you can redistribute it and/or modify
4
 
# it under the terms of the GNU General Public License as published by
5
 
# the Free Software Foundation; either version 2 of the License, or
6
 
# (at your option) any later version.
7
 
 
8
 
# This program is distributed in the hope that it will be useful,
9
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
# GNU General Public License for more details.
12
 
 
13
 
# You should have received a copy of the GNU General Public License
14
 
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
 
 
17
 
def max_distance(node, ancestors, distances, root_descendants):
18
 
    """Calculate the max distance to an ancestor.  
19
 
    Return None if not all possible ancestors have known distances"""
20
 
    best = None
21
 
    if node in distances:
22
 
        best = distances[node]
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
27
 
        # An ancestor which is not listed in ancestors will never be in
28
 
        # distances, so we pretend it never existed.
29
 
        if ancestor not in ancestors:
30
 
            continue
31
 
        if ancestor not in distances:
32
 
            return None
33
 
        if best is None or distances[ancestor] > best:
34
 
            best = distances[ancestor] + 1
35
 
    return best
36
 
 
37
 
    
38
 
def node_distances(graph, ancestors, start, root_descendants=None):
39
 
    """Produce a list of nodes, sorted by distance from a start node.
40
 
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
41
 
    backwards seemed too complicated.
42
 
 
43
 
    For each node, we walk its descendants.  If all the descendant's ancestors
44
 
    have a max-distance-to-start, (excluding ones that can never reach start),
45
 
    we calculate their max-distance-to-start, and schedule their descendants.
46
 
 
47
 
    So when a node's last parent acquires a distance, it will acquire a
48
 
    distance on the next iteration.
49
 
 
50
 
    Once we know the max distances for all nodes, we can return a list sorted
51
 
    by distance, farthest first.
52
 
    """
53
 
    distances = {start: 0}
54
 
    lines = set([start])
55
 
    while len(lines) > 0:
56
 
        new_lines = set()
57
 
        for line in lines:
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)
63
 
                if distance is None:
64
 
                    continue
65
 
                distances[descendant] = distance
66
 
                new_lines.add(descendant)
67
 
        lines = new_lines
68
 
    return distances
69
 
 
70
 
def farthest_nodes(graph, ancestors, start):
71
 
    def by_distance(n):
72
 
        return distances[n],n
73
 
 
74
 
    distances = node_distances(graph, ancestors, start)
75
 
    node_list = distances.keys()
76
 
    node_list.sort(key=by_distance, reverse=True)
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