Rev 5845: (jelmer) Remove bzrlib.deprecated_graph. (Jelmer Vernooij) in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Tue May 10 08:39:45 UTC 2011
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 5845 [merge]
revision-id: pqm at pqm.ubuntu.com-20110510083940-55j6je6dlqrnhmqf
parent: pqm at pqm.ubuntu.com-20110509153914-wbwvbi34ohzwpv9k
parent: jelmer at samba.org-20110510074615-eptod049ndjxc4i7
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Tue 2011-05-10 08:39:40 +0000
message:
(jelmer) Remove bzrlib.deprecated_graph. (Jelmer Vernooij)
removed:
bzrlib/deprecated_graph.py graph.py-20050905070950-b47dce53236c5e48
bzrlib/tests/test_deprecated_graph.py testgraph.py-20050905070950-42e6c958106610fd
modified:
bzrlib/tests/__init__.py selftest.py-20050531073622-8d0e3c8845c97a64
doc/en/release-notes/bzr-2.4.txt bzr2.4.txt-20110114053217-k7ym9jfz243fddjm-1
=== removed file 'bzrlib/deprecated_graph.py'
--- a/bzrlib/deprecated_graph.py 2009-03-23 14:59:43 +0000
+++ b/bzrlib/deprecated_graph.py 1970-01-01 00:00:00 +0000
@@ -1,161 +0,0 @@
-# Copyright (C) 2005, 2008 Canonical Ltd
-#
-# This program is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation; either version 2 of the License, or
-# (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
-
-
-def max_distance(node, ancestors, distances, root_descendants):
- """Calculate the max distance to an ancestor.
- Return None if not all possible ancestors have known distances"""
- best = None
- if node in distances:
- best = distances[node]
- for ancestor in ancestors[node]:
- # skip ancestors we will never traverse:
- if root_descendants is not None and ancestor not in root_descendants:
- continue
- # An ancestor which is not listed in ancestors will never be in
- # distances, so we pretend it never existed.
- if ancestor not in ancestors:
- continue
- if ancestor not in distances:
- return None
- if best is None or distances[ancestor]+1 > best:
- best = distances[ancestor] + 1
- return best
-
-
-def node_distances(graph, ancestors, start, root_descendants=None):
- """Produce a list of nodes, sorted by distance from a start node.
- This is an algorithm devised by Aaron Bentley, because applying Dijkstra
- backwards seemed too complicated.
-
- For each node, we walk its descendants. If all the descendant's ancestors
- have a max-distance-to-start, (excluding ones that can never reach start),
- we calculate their max-distance-to-start, and schedule their descendants.
-
- So when a node's last parent acquires a distance, it will acquire a
- distance on the next iteration.
-
- Once we know the max distances for all nodes, we can return a list sorted
- by distance, farthest first.
- """
- distances = {start: 0}
- lines = set([start])
- while len(lines) > 0:
- new_lines = set()
- for line in lines:
- line_descendants = graph[line]
- for descendant in line_descendants:
- distance = max_distance(descendant, ancestors, distances,
- root_descendants)
- if distance is None:
- continue
- distances[descendant] = distance
- new_lines.add(descendant)
- lines = new_lines
- return distances
-
-def nodes_by_distance(distances):
- """Return a list of nodes sorted by distance"""
- def by_distance(n):
- return distances[n],n
-
- node_list = distances.keys()
- node_list.sort(key=by_distance, reverse=True)
- return node_list
-
-def select_farthest(distances, common):
- """Return the farthest common node, or None if no node qualifies."""
- node_list = nodes_by_distance(distances)
- for node in node_list:
- if node in common:
- return node
-
-def all_descendants(descendants, start):
- """Produce a set of all descendants of the start node.
- The input is a map of node->list of descendants for a graph encompassing
- start.
- """
- result = set()
- lines = set([start])
- while len(lines) > 0:
- new_lines = set()
- for line in lines:
- if line not in descendants:
- continue
- for descendant in descendants[line]:
- if descendant in result:
- continue
- result.add(descendant)
- new_lines.add(descendant)
- lines = new_lines
- return result
-
-
-class Graph(object):
- """A graph object which can memoise and cache results for performance."""
-
- def __init__(self):
- super(Graph, self).__init__()
- self.roots = set([])
- self.ghosts = set([])
- self._graph_ancestors = {}
- self._graph_descendants = {}
-
- def add_ghost(self, node_id):
- """Add a ghost to the graph."""
- self.ghosts.add(node_id)
- self._ensure_descendant(node_id)
-
- def add_node(self, node_id, parent_ids):
- """Add node_id to the graph with parent_ids as its parents."""
- if len(parent_ids) == 0:
- self.roots.add(node_id)
- self._graph_ancestors[node_id] = list(parent_ids)
- self._ensure_descendant(node_id)
- for parent in parent_ids:
- self._ensure_descendant(parent)
- self._graph_descendants[parent][node_id] = 1
-
- def _ensure_descendant(self, node_id):
- """Ensure that a descendant lookup for node_id will work."""
- if not node_id in self._graph_descendants:
- self._graph_descendants[node_id] = {}
-
- def get_ancestors(self):
- """Return a dictionary of graph node:ancestor_list entries."""
- return dict(self._graph_ancestors.items())
-
- def get_ancestry(self, node_id, topo_sorted=True):
- """Return the inclusive ancestors of node_id in topological order."""
- # maybe optimise this ?
- from bzrlib.tsort import topo_sort
- result = {}
- pending = set([node_id])
- while len(pending):
- current = pending.pop()
- parents = self._graph_ancestors[current]
- parents = [parent for parent in parents if parent not in self.ghosts]
- result[current] = parents
- for parent in parents:
- if parent not in result and parent not in pending:
- pending.add(parent)
- if not topo_sorted:
- return result.keys()
- return topo_sort(result.items())
-
- def get_descendants(self):
- """Return a dictionary of graph node:child_node:distance entries."""
- return dict(self._graph_descendants.items())
=== modified file 'bzrlib/tests/__init__.py'
--- a/bzrlib/tests/__init__.py 2011-04-21 01:19:32 +0000
+++ b/bzrlib/tests/__init__.py 2011-05-10 07:46:15 +0000
@@ -3776,7 +3776,6 @@
'bzrlib.tests.test_decorators',
'bzrlib.tests.test_delta',
'bzrlib.tests.test_debug',
- 'bzrlib.tests.test_deprecated_graph',
'bzrlib.tests.test_diff',
'bzrlib.tests.test_directory_service',
'bzrlib.tests.test_dirstate',
=== removed file 'bzrlib/tests/test_deprecated_graph.py'
--- a/bzrlib/tests/test_deprecated_graph.py 2009-03-23 14:59:43 +0000
+++ b/bzrlib/tests/test_deprecated_graph.py 1970-01-01 00:00:00 +0000
@@ -1,80 +0,0 @@
-# Copyright (C) 2005, 2006 Canonical Ltd
-#
-# This program is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation; either version 2 of the License, or
-# (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
-
-from bzrlib.tests import TestCase
-from bzrlib.deprecated_graph import node_distances, nodes_by_distance, Graph
-
-
-class TestBase(TestCase):
-
- def edge_add(self, *args):
- for start, end in zip(args[:-1], args[1:]):
- if start not in self.graph:
- self.graph[start] = {}
- if end not in self.graph:
- self.graph[end] = {}
- self.graph[start][end] = 1
-
- def setUp(self):
- TestCase.setUp(self)
- self.graph = {}
- self.edge_add('A', 'B', 'C', 'D')
- self.edge_add('A', 'E', 'F', 'C')
- self.edge_add('A', 'G', 'H', 'I', 'B')
- self.edge_add('A', 'J', 'K', 'L', 'M', 'N')
- self.edge_add('O', 'N')
-
- def node_descendants(self):
- descendants = {'A':set()}
- for node in self.graph:
- for ancestor in self.graph[node]:
- if ancestor not in descendants:
- descendants[ancestor] = set()
- descendants[ancestor].add(node)
- return descendants
-
- def test_distances(self):
- descendants = self.node_descendants()
- distances = node_distances(self.graph, descendants, 'A')
- nodes = nodes_by_distance(distances)
- self.assertEqual(nodes[0], 'D')
- self.assert_(nodes[1] in ('N', 'C'))
- self.assert_(nodes[2] in ('N', 'C'))
- self.assert_(nodes[3] in ('B', 'M'))
- self.assert_(nodes[4] in ('B', 'M'))
-
- #Ensure we don't shortcut through B when there's only a difference of
- # 1 in distance
- self.graph = {}
- self.edge_add('A', 'B', 'C')
- self.edge_add('A', 'D', 'E', 'C')
- descendants = self.node_descendants()
- distances = node_distances(self.graph, descendants, 'A')
- self.assertEqual(distances['C'], 3)
-
-
-class TestGraph(TestCase):
-
- def test_get_descendants(self):
- # Graph objects let you get a descendants graph in
- # node: {direct-children:distance} which contains
- # known children, including ghost children
- graph = Graph()
- graph.add_ghost('ghost')
- graph.add_node('rev1', ['ghost'])
- # check the result contains ghosts:
- self.assertEqual({'ghost': {'rev1': 1}, 'rev1': {}},
- graph.get_descendants())
=== modified file 'doc/en/release-notes/bzr-2.4.txt'
--- a/doc/en/release-notes/bzr-2.4.txt 2011-05-09 11:59:04 +0000
+++ b/doc/en/release-notes/bzr-2.4.txt 2011-05-10 07:46:15 +0000
@@ -485,6 +485,10 @@
``ControlDir.sprout`` no longer has a default implementation; it now
raises ``NotImplementedError``. (Jelmer Vernooij, #717937)
+* ``bzrlib.deprecated_graph`` has been removed. ``bzrlib.graph``
+ scales better tree and should be used instead.
+ (Jelmer Vernooij, #733612)
+
* ``ControlDirFormat.register_format`` has been removed. Instead,
``Prober`` implementations should now implement a ``known_formats``
method. (Jelmer Vernooij)
More information about the bazaar-commits
mailing list