← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2007-05-31 20:29:04 UTC
  • mto: This revision was merged to the branch mainline in revision 2499.
  • Revision ID: john@arbash-meinel.com-20070531202904-34h7ygudo7qq9ha1
Update the code so that symlinks aren't cached at incorrect times
and fix the tests so that they don't assume files and symlinks
get cached even when the timestamp doesn't declare them 'safe'.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2005, 2008 Canonical Ltd
 
1
# Copyright (C) 2005 Canonical Ltd
2
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
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
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
 
 
18
from bzrlib.tsort import topo_sort
16
19
 
17
20
 
18
21
def max_distance(node, ancestors, distances, root_descendants):
19
 
    """Calculate the max distance to an ancestor.
 
22
    """Calculate the max distance to an ancestor.  
20
23
    Return None if not all possible ancestors have known distances"""
21
24
    best = None
22
25
    if node in distances:
35
38
            best = distances[ancestor] + 1
36
39
    return best
37
40
 
38
 
 
 
41
    
39
42
def node_distances(graph, ancestors, start, root_descendants=None):
40
43
    """Produce a list of nodes, sorted by distance from a start node.
41
44
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
57
60
        new_lines = set()
58
61
        for line in lines:
59
62
            line_descendants = graph[line]
 
63
            assert line not in line_descendants, "%s refers to itself" % line
60
64
            for descendant in line_descendants:
61
65
                distance = max_distance(descendant, ancestors, distances,
62
66
                                        root_descendants)
121
125
 
122
126
    def add_node(self, node_id, parent_ids):
123
127
        """Add node_id to the graph with parent_ids as its parents."""
124
 
        if len(parent_ids) == 0:
 
128
        if parent_ids == []:
125
129
            self.roots.add(node_id)
126
130
        self._graph_ancestors[node_id] = list(parent_ids)
127
131
        self._ensure_descendant(node_id)
128
132
        for parent in parent_ids:
129
133
            self._ensure_descendant(parent)
130
134
            self._graph_descendants[parent][node_id] = 1
131
 
 
 
135
        
132
136
    def _ensure_descendant(self, node_id):
133
137
        """Ensure that a descendant lookup for node_id will work."""
134
138
        if not node_id in self._graph_descendants:
138
142
        """Return a dictionary of graph node:ancestor_list entries."""
139
143
        return dict(self._graph_ancestors.items())
140
144
 
141
 
    def get_ancestry(self, node_id, topo_sorted=True):
 
145
    def get_ancestry(self, node_id):
142
146
        """Return the inclusive ancestors of node_id in topological order."""
143
147
        # maybe optimise this ?
144
 
        from bzrlib.tsort import topo_sort
145
148
        result = {}
146
149
        pending = set([node_id])
147
150
        while len(pending):
152
155
            for parent in parents:
153
156
                if parent not in result and parent not in pending:
154
157
                    pending.add(parent)
155
 
        if not topo_sorted:
156
 
            return result.keys()
157
158
        return topo_sort(result.items())
158
159
 
159
160
    def get_descendants(self):