← Back to branch summary

~bzr/ubuntu/lucid/bzr/beta-ppa

« back to all changes in this revision

Viewing changes to bzrlib/deprecated_graph.py

  • Committer: Martin Pool
  • Date: 2010-07-02 07:29:40 UTC
  • mfrom: (129.1.7 packaging-karmic)
  • Revision ID: mbp@sourcefrog.net-20100702072940-hpzq5elg8wjve8rh
http://bugs.debian.org/452024
http://bugs.debian.org/464688
http://bugs.debian.org/523595
http://bugs.debian.org/526233
http://bugs.debian.org/537708
http://bugs.debian.org/555336
http://bugs.debian.org/555343
https://launchpad.net/bugs/249452
https://launchpad.net/bugs/385074
* PPA rebuild.
* PPA rebuild for Karmic.
* PPA rebuild for Jaunty.
* PPA rebuild for Hardy.
* From postinst, actually remove the example bash completion scripts.
  (LP: #249452)
* New upstream release.
* New upstream release.
* New upstream release.
* Revert change to Build-depends: Dapper does not have python-central.
  Should be python-support..
* Target ppa..
* Target ppa..
* Target ppa..
* Target ppa..
* New upstream release.
* Switch to dpkg-source 3.0 (quilt) format.
* Bump standards version to 3.8.4.
* Remove embedded copy of python-configobj. Closes: #555336
* Remove embedded copy of python-elementtree. Closes: #555343
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* debian/control: Fix obsolete-relation-form-in-source
  lintian warning. 
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split out docs into bzr-doc package.
* New upstream release.
* Added John Francesco Ferlito to Uploaders.
* Fix install path to quick-reference guide
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again, again.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to path changes.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Bump standards version to 3.8.3.
* Remove unused patch system.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix copy and paste tab error in .install file
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
 + Fixes compatibility with Python 2.4. Closes: #537708
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream version.
* Bump standards version to 3.8.2.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add python-pyrex to build-deps to ensure C extensions are always build.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix API compatibility version. (Closes: #526233)
* New upstream release.
  + Fixes default format for upgrade command. (Closes: #464688)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add missing dependency on zlib development library. (Closes:
  #523595)
* Add zlib build-depends.
* Add zlib build-depends.
* Add zlib build-depends.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Move to section vcs.
* Bump standards version to 3.8.1.
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Recommend ca-certificates. (Closes: #452024)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Update watch file. bazaar now uses launchpad to host its sources.
* Remove patch for inventory root revision copy, applied upstream.
* New upstream release.
* New upstream release.
* New upstream release
* Force removal of files installed in error to /etc/bash_completion.d/
  (LP: #249452)
* New upstream release.
* New upstream release
* New upstream release.
* Bump standards version.
* Include patch for inventory root revision copy, required for bzr-svn.
* New upstream release.
* Remove unused lintian overrides.
* Correct the package version not to be native.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Final 1.5 release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add myself as a co-maintainer.
* Add a Dm-Upload-Allowed: yes header.
* New upstream bugfix release.
* New upstream release.
* Final 1.3 release.
* New upstream release.
* First release candidate of the upcoming 1.3 release.
* Rebuild to fix the problem caused by a build with a broken python-central.
* New upstream release.
* Rebuild for dapper PPA.
* Apply Lamont's patches to fix build-dependencies on dapper.
  (See: https://bugs.launchpad.net/bzr/+bug/189915)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/deprecated_graph.py
 
1
# Copyright (C) 2005, 2008 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
 
 
18
def max_distance(node, ancestors, distances, root_descendants):
 
19
    """Calculate the max distance to an ancestor.
 
20
    Return None if not all possible ancestors have known distances"""
 
21
    best = None
 
22
    if node in distances:
 
23
        best = distances[node]
 
24
    for ancestor in ancestors[node]:
 
25
        # skip ancestors we will never traverse:
 
26
        if root_descendants is not None and ancestor not in root_descendants:
 
27
            continue
 
28
        # An ancestor which is not listed in ancestors will never be in
 
29
        # distances, so we pretend it never existed.
 
30
        if ancestor not in ancestors:
 
31
            continue
 
32
        if ancestor not in distances:
 
33
            return None
 
34
        if best is None or distances[ancestor]+1 > best:
 
35
            best = distances[ancestor] + 1
 
36
    return best
 
37
 
 
38
 
 
39
def node_distances(graph, ancestors, start, root_descendants=None):
 
40
    """Produce a list of nodes, sorted by distance from a start node.
 
41
    This is an algorithm devised by Aaron Bentley, because applying Dijkstra
 
42
    backwards seemed too complicated.
 
43
 
 
44
    For each node, we walk its descendants.  If all the descendant's ancestors
 
45
    have a max-distance-to-start, (excluding ones that can never reach start),
 
46
    we calculate their max-distance-to-start, and schedule their descendants.
 
47
 
 
48
    So when a node's last parent acquires a distance, it will acquire a
 
49
    distance on the next iteration.
 
50
 
 
51
    Once we know the max distances for all nodes, we can return a list sorted
 
52
    by distance, farthest first.
 
53
    """
 
54
    distances = {start: 0}
 
55
    lines = set([start])
 
56
    while len(lines) > 0:
 
57
        new_lines = set()
 
58
        for line in lines:
 
59
            line_descendants = graph[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 nodes_by_distance(distances):
 
71
    """Return a list of nodes sorted by distance"""
 
72
    def by_distance(n):
 
73
        return distances[n],n
 
74
 
 
75
    node_list = distances.keys()
 
76
    node_list.sort(key=by_distance, reverse=True)
 
77
    return node_list
 
78
 
 
79
def select_farthest(distances, common):
 
80
    """Return the farthest common node, or None if no node qualifies."""
 
81
    node_list = nodes_by_distance(distances)
 
82
    for node in node_list:
 
83
        if node in common:
 
84
            return node
 
85
 
 
86
def all_descendants(descendants, start):
 
87
    """Produce a set of all descendants of the start node.
 
88
    The input is a map of node->list of descendants for a graph encompassing
 
89
    start.
 
90
    """
 
91
    result = set()
 
92
    lines = set([start])
 
93
    while len(lines) > 0:
 
94
        new_lines = set()
 
95
        for line in lines:
 
96
            if line not in descendants:
 
97
                continue
 
98
            for descendant in descendants[line]:
 
99
                if descendant in result:
 
100
                    continue
 
101
                result.add(descendant)
 
102
                new_lines.add(descendant)
 
103
        lines = new_lines
 
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())