/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/deprecated_graph.py

  • Committer: Robert Collins
  • Date: 2007-10-05 02:41:37 UTC
  • mto: (2592.3.166 repository)
  • mto: This revision was merged to the branch mainline in revision 2896.
  • Revision ID: robertc@robertcollins.net-20071005024137-kn7brcu07nu8cwl1
* The class ``bzrlib.repofmt.knitrepo.KnitRepository3`` has been folded into
  ``KnitRepository`` by parameters to the constructor. (Robert Collins)
* ``bzrlib.xml_serializer.Serializer`` is now responsible for checking that
  mandatory attributes are present on serialisation and deserialisation.
  This fixes some holes in API usage and allows better separation between
  physical storage and object serialisation. (Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/deprecated_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)
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:
141
145
    def get_ancestry(self, node_id, topo_sorted=True):
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):