/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Robert Collins
  • Date: 2005-10-16 22:31:25 UTC
  • mto: This revision was merged to the branch mainline in revision 1458.
  • Revision ID: robertc@lifelesslap.robertcollins.net-20051016223125-26d4401cb94b7b82
Branch.relpath has been moved to WorkingTree.relpath.

WorkingTree no no longer takes an inventory, rather it takes an optional branch
parameter, and if None is given will open the branch at basedir implicitly.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2005, 2008 Canonical Ltd
2
 
#
 
1
# (C) 2005 Canonical
 
2
 
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
#
 
7
 
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
12
 
#
 
12
 
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
16
 
18
17
def max_distance(node, ancestors, distances, root_descendants):
19
 
    """Calculate the max distance to an ancestor.
 
18
    """Calculate the max distance to an ancestor.  
20
19
    Return None if not all possible ancestors have known distances"""
21
20
    best = None
22
21
    if node in distances:
35
34
            best = distances[ancestor] + 1
36
35
    return best
37
36
 
38
 
 
 
37
    
39
38
def node_distances(graph, ancestors, start, root_descendants=None):
40
39
    """Produce a list of nodes, sorted by distance from a start node.
41
40
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
57
56
        new_lines = set()
58
57
        for line in lines:
59
58
            line_descendants = graph[line]
 
59
            assert line not in line_descendants, "%s refers to itself" % line
60
60
            for descendant in line_descendants:
61
61
                distance = max_distance(descendant, ancestors, distances,
62
62
                                        root_descendants)
102
102
                new_lines.add(descendant)
103
103
        lines = new_lines
104
104
    return result
105
 
 
106
 
 
107
 
class Graph(object):
108
 
    """A graph object which can memoise and cache results for performance."""
109
 
 
110
 
    def __init__(self):
111
 
        super(Graph, self).__init__()
112
 
        self.roots = set([])
113
 
        self.ghosts = set([])
114
 
        self._graph_ancestors = {}
115
 
        self._graph_descendants = {}
116
 
 
117
 
    def add_ghost(self, node_id):
118
 
        """Add a ghost to the graph."""
119
 
        self.ghosts.add(node_id)
120
 
        self._ensure_descendant(node_id)
121
 
 
122
 
    def add_node(self, node_id, parent_ids):
123
 
        """Add node_id to the graph with parent_ids as its parents."""
124
 
        if len(parent_ids) == 0:
125
 
            self.roots.add(node_id)
126
 
        self._graph_ancestors[node_id] = list(parent_ids)
127
 
        self._ensure_descendant(node_id)
128
 
        for parent in parent_ids:
129
 
            self._ensure_descendant(parent)
130
 
            self._graph_descendants[parent][node_id] = 1
131
 
 
132
 
    def _ensure_descendant(self, node_id):
133
 
        """Ensure that a descendant lookup for node_id will work."""
134
 
        if not node_id in self._graph_descendants:
135
 
            self._graph_descendants[node_id] = {}
136
 
 
137
 
    def get_ancestors(self):
138
 
        """Return a dictionary of graph node:ancestor_list entries."""
139
 
        return dict(self._graph_ancestors.items())
140
 
 
141
 
    def get_ancestry(self, node_id, topo_sorted=True):
142
 
        """Return the inclusive ancestors of node_id in topological order."""
143
 
        # maybe optimise this ?
144
 
        from bzrlib.tsort import topo_sort
145
 
        result = {}
146
 
        pending = set([node_id])
147
 
        while len(pending):
148
 
            current = pending.pop()
149
 
            parents = self._graph_ancestors[current]
150
 
            parents = [parent for parent in parents if parent not in self.ghosts]
151
 
            result[current] = parents
152
 
            for parent in parents:
153
 
                if parent not in result and parent not in pending:
154
 
                    pending.add(parent)
155
 
        if not topo_sorted:
156
 
            return result.keys()
157
 
        return topo_sort(result.items())
158
 
 
159
 
    def get_descendants(self):
160
 
        """Return a dictionary of graph node:child_node:distance entries."""
161
 
        return dict(self._graph_descendants.items())