← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Robert Collins
  • Date: 2005-08-24 12:54:49 UTC
  • mto: (974.1.50) (1185.1.10) (1092.3.1)
  • mto: This revision was merged to the branch mainline in revision 1139.
  • Revision ID: robertc@robertcollins.net-20050824125449-4cc5745568016866
update hacking with some test foo

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2005 Canonical Ltd
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
 
 
18
 
from bzrlib.tsort import topo_sort
19
 
 
20
 
 
21
 
def max_distance(node, ancestors, distances, root_descendants):
22
 
    """Calculate the max distance to an ancestor.  
23
 
    Return None if not all possible ancestors have known distances"""
24
 
    best = None
25
 
    if node in distances:
26
 
        best = distances[node]
27
 
    for ancestor in ancestors[node]:
28
 
        # skip ancestors we will never traverse:
29
 
        if root_descendants is not None and ancestor not in root_descendants:
30
 
            continue
31
 
        # An ancestor which is not listed in ancestors will never be in
32
 
        # distances, so we pretend it never existed.
33
 
        if ancestor not in ancestors:
34
 
            continue
35
 
        if ancestor not in distances:
36
 
            return None
37
 
        if best is None or distances[ancestor]+1 > best:
38
 
            best = distances[ancestor] + 1
39
 
    return best
40
 
 
41
 
    
42
 
def node_distances(graph, ancestors, start, root_descendants=None):
43
 
    """Produce a list of nodes, sorted by distance from a start node.
44
 
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
45
 
    backwards seemed too complicated.
46
 
 
47
 
    For each node, we walk its descendants.  If all the descendant's ancestors
48
 
    have a max-distance-to-start, (excluding ones that can never reach start),
49
 
    we calculate their max-distance-to-start, and schedule their descendants.
50
 
 
51
 
    So when a node's last parent acquires a distance, it will acquire a
52
 
    distance on the next iteration.
53
 
 
54
 
    Once we know the max distances for all nodes, we can return a list sorted
55
 
    by distance, farthest first.
56
 
    """
57
 
    distances = {start: 0}
58
 
    lines = set([start])
59
 
    while len(lines) > 0:
60
 
        new_lines = set()
61
 
        for line in lines:
62
 
            line_descendants = graph[line]
63
 
            assert line not in line_descendants, "%s refers to itself" % line
64
 
            for descendant in line_descendants:
65
 
                distance = max_distance(descendant, ancestors, distances,
66
 
                                        root_descendants)
67
 
                if distance is None:
68
 
                    continue
69
 
                distances[descendant] = distance
70
 
                new_lines.add(descendant)
71
 
        lines = new_lines
72
 
    return distances
73
 
 
74
 
def nodes_by_distance(distances):
75
 
    """Return a list of nodes sorted by distance"""
76
 
    def by_distance(n):
77
 
        return distances[n],n
78
 
 
79
 
    node_list = distances.keys()
80
 
    node_list.sort(key=by_distance, reverse=True)
81
 
    return node_list
82
 
 
83
 
def select_farthest(distances, common):
84
 
    """Return the farthest common node, or None if no node qualifies."""
85
 
    node_list = nodes_by_distance(distances)
86
 
    for node in node_list:
87
 
        if node in common:
88
 
            return node
89
 
 
90
 
def all_descendants(descendants, start):
91
 
    """Produce a set of all descendants of the start node.
92
 
    The input is a map of node->list of descendants for a graph encompassing
93
 
    start.
94
 
    """
95
 
    result = set()
96
 
    lines = set([start])
97
 
    while len(lines) > 0:
98
 
        new_lines = set()
99
 
        for line in lines:
100
 
            if line not in descendants:
101
 
                continue
102
 
            for descendant in descendants[line]:
103
 
                if descendant in result:
104
 
                    continue
105
 
                result.add(descendant)
106
 
                new_lines.add(descendant)
107
 
        lines = new_lines
108
 
    return result
109
 
 
110
 
 
111
 
class Graph(object):
112
 
    """A graph object which can memoise and cache results for performance."""
113
 
 
114
 
    def __init__(self):
115
 
        super(Graph, self).__init__()
116
 
        self.roots = set([])
117
 
        self.ghosts = set([])
118
 
        self._graph_ancestors = {}
119
 
        self._graph_descendants = {}
120
 
 
121
 
    def add_ghost(self, node_id):
122
 
        """Add a ghost to the graph."""
123
 
        self.ghosts.add(node_id)
124
 
        self._ensure_descendant(node_id)
125
 
 
126
 
    def add_node(self, node_id, parent_ids):
127
 
        """Add node_id to the graph with parent_ids as its parents."""
128
 
        if parent_ids == []:
129
 
            self.roots.add(node_id)
130
 
        self._graph_ancestors[node_id] = list(parent_ids)
131
 
        self._ensure_descendant(node_id)
132
 
        for parent in parent_ids:
133
 
            self._ensure_descendant(parent)
134
 
            self._graph_descendants[parent][node_id] = 1
135
 
        
136
 
    def _ensure_descendant(self, node_id):
137
 
        """Ensure that a descendant lookup for node_id will work."""
138
 
        if not node_id in self._graph_descendants:
139
 
            self._graph_descendants[node_id] = {}
140
 
 
141
 
    def get_ancestors(self):
142
 
        """Return a dictionary of graph node:ancestor_list entries."""
143
 
        return dict(self._graph_ancestors.items())
144
 
 
145
 
    def get_ancestry(self, node_id):
146
 
        """Return the inclusive ancestors of node_id in topological order."""
147
 
        # maybe optimise this ?
148
 
        result = {}
149
 
        pending = set([node_id])
150
 
        while len(pending):
151
 
            current = pending.pop()
152
 
            parents = self._graph_ancestors[current]
153
 
            parents = [parent for parent in parents if parent not in self.ghosts]
154
 
            result[current] = parents
155
 
            for parent in parents:
156
 
                if parent not in result and parent not in pending:
157
 
                    pending.add(parent)
158
 
        return topo_sort(result.items())
159
 
 
160
 
    def get_descendants(self):
161
 
        """Return a dictionary of graph node:child_node:distance entries."""
162
 
        return dict(self._graph_descendants.items())