/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: Martin Pool
  • Date: 2005-06-28 03:02:31 UTC
  • Revision ID: mbp@sourcefrog.net-20050628030231-d311e4ebcd467ef4
Merge John's import-speedup branch:

                                                                                         
  777 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:32 -0500
      revision-id: john@arbash-meinel.com-20050627032031-e82a50db3863b18e
      bzr selftest was not using the correct bzr

  776 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:22 -0500
      revision-id: john@arbash-meinel.com-20050627032021-c9f21fde989ddaee
      Add was using an old mutter

  775 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:02:33 -0500
      revision-id: john@arbash-meinel.com-20050627030233-9165cfe98fc63298
      Cleaned up to be less different

  774 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:54:53 -0500
      revision-id: john@arbash-meinel.com-20050627025452-4260d0e744edef43
      Allow BZR_PLUGIN_PATH='' to negate plugin loading.

  773 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:49:34 -0500
      revision-id: john@arbash-meinel.com-20050627024933-b7158f67b7b9eae5
      Finished the previous cleanup (allowing load_plugins to be called twice)

  772 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:45:08 -0500
      revision-id: john@arbash-meinel.com-20050627024508-723b1df510d196fc
      Work on making the tests pass. versioning.py is calling run_cmd directly, but plugins have been loaded.

  771 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:32:29 -0500
      revision-id: john@arbash-meinel.com-20050627023228-79972744d7c53e15
      Got it down a little bit more by removing import of tree and inventory.

  770 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:26:05 -0500
      revision-id: john@arbash-meinel.com-20050627022604-350b9773ef622f95
      Reducing the number of import from bzrlib/__init__.py and bzrlib/branch.py

  769 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:32:25 -0500
      revision-id: john@arbash-meinel.com-20050627013225-32dd044f10d23948
      Updated revision.py and xml.py to include SubElement.

  768 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:56 -0500
      revision-id: john@arbash-meinel.com-20050627010356-ee66919e1c377faf
      Minor typo

  767 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:13 -0500
      revision-id: john@arbash-meinel.com-20050627010312-40d024007eb85051
      Caching the import

  766 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:51:47 -0500
      revision-id: john@arbash-meinel.com-20050627005147-5281c99e48ed1834
      Created wrapper functions for lazy import of ElementTree

  765 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:46:37 -0500
      revision-id: john@arbash-meinel.com-20050627004636-bf432902004a94c5
      Removed all of the test imports of cElementTree

  764 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:43:59 -0500
      revision-id: john@arbash-meinel.com-20050627004358-d137fbe9570dd71b
      Trying to make bzr startup faster.

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())