Rev 4610: Implement a very basic version of KnownGraph.topo_sort that just in http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted
John Arbash Meinel
john at arbash-meinel.com
Thu Aug 13 21:59:21 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted
------------------------------------------------------------
revno: 4610
revision-id: john at arbash-meinel.com-20090813205913-fygdc0ycyio81i03
parent: john at arbash-meinel.com-20090813203734-2sq60sc68wzrj0z2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Thu 2009-08-13 15:59:13 -0500
message:
Implement a very basic version of KnownGraph.topo_sort that just
thunks over to the tsort implementation.
Add some tests which ensure that things are working.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py 2009-07-08 20:58:10 +0000
+++ b/bzrlib/_known_graph_py.py 2009-08-13 20:59:13 +0000
@@ -171,3 +171,9 @@
self._known_heads[heads_key] = heads
return heads
+ def topo_sort(self):
+ from bzrlib import tsort
+ as_parent_map = dict((node.key, node.parent_keys)
+ for node in self._nodes.itervalues()
+ if node.parent_keys is not None)
+ return tsort.topo_sort(as_parent_map)
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx 2009-07-14 16:10:32 +0000
+++ b/bzrlib/_known_graph_pyx.pyx 2009-08-13 20:59:13 +0000
@@ -335,3 +335,16 @@
if self.do_cache:
PyDict_SetItem(self._known_heads, heads_key, heads)
return heads
+
+ def topo_sort(self):
+ cdef _KnownGraphNode node, parent
+ from bzrlib import tsort
+ as_parent_map = {}
+ for node in self._nodes.itervalues():
+ if node.parents is None:
+ continue
+ parent_keys = []
+ for parent in node.parents:
+ parent_keys.append(parent.key)
+ as_parent_map[node.key] = parent_keys
+ return tsort.topo_sort(as_parent_map)
=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py 2009-07-08 20:58:10 +0000
+++ b/bzrlib/tests/test__known_graph.py 2009-08-13 20:59:13 +0000
@@ -85,6 +85,25 @@
node = graph._nodes[rev]
self.assertEqual(gdfo, node.gdfo)
+ def assertTopoSortOrder(self, ancestry):
+ """Check topo_sort and iter_topo_order is genuinely topological order.
+
+ For every child in the graph, check if it comes after all of it's
+ parents.
+ """
+ graph = self.module.KnownGraph(ancestry)
+ sort_result = graph.topo_sort()
+ node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
+ for node in sort_result:
+ parents = ancestry[node]
+ for parent in parents:
+ if parent not in ancestry:
+ # ghost
+ continue
+ if node_idx[node] <= node_idx[parent]:
+ self.fail("parent %s must come before child %s:\n%s"
+ % (parent, node, sort_result))
+
def test_children_ancestry1(self):
graph = self.make_known_graph(test_graph.ancestry_1)
self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
@@ -227,3 +246,53 @@
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
+
+ def test_topo_sort_empty(self):
+ """TopoSort empty list"""
+ self.assertTopoSortOrder({})
+
+ def test_topo_sort_easy(self):
+ """TopoSort list with one node"""
+ self.assertTopoSortOrder({0: []})
+
+ def test_topo_sort_cycle(self):
+ """TopoSort traps graph with cycles"""
+ g = self.module.KnownGraph({0: [1],
+ 1: [0]})
+ self.assertRaises(errors.GraphCycleError, g.topo_sort)
+
+ def test_topo_sort_cycle_2(self):
+ """TopoSort traps graph with longer cycle"""
+ g = self.module.KnownGraph({0: [1],
+ 1: [2],
+ 2: [0]})
+ self.assertRaises(errors.GraphCycleError, g.topo_sort)
+
+ def test_topo_sort_1(self):
+ """TopoSort simple nontrivial graph"""
+ self.assertTopoSortOrder({0: [3],
+ 1: [4],
+ 2: [1, 4],
+ 3: [],
+ 4: [0, 3]})
+
+ def test_topo_sort_partial(self):
+ """Topological sort with partial ordering.
+
+ Multiple correct orderings are possible, so test for
+ correctness, not for exact match on the resulting list.
+ """
+ self.assertTopoSortOrder({0: [],
+ 1: [0],
+ 2: [0],
+ 3: [0],
+ 4: [1, 2, 3],
+ 5: [1, 2],
+ 6: [1, 2],
+ 7: [2, 3],
+ 8: [0, 1, 4, 5, 6]})
+
+ def test_topo_sort_ghost_parent(self):
+ """Sort nodes, but don't include some parents in the output"""
+ self.assertTopoSortOrder({0: [1],
+ 1: [2]})
=== modified file 'bzrlib/tests/test_tsort.py'
--- a/bzrlib/tests/test_tsort.py 2009-07-30 12:55:32 +0000
+++ b/bzrlib/tests/test_tsort.py 2009-08-13 20:59:13 +0000
@@ -40,18 +40,21 @@
TopoSorter(graph).iter_topo_order())
def assertSortAndIterateOrder(self, graph):
- """Check that sorting and iter_topo_order on graph really results in topological order.
+ """Check topo_sort and iter_topo_order is genuinely topological order.
- For every child in the graph, check if it comes after all of it's parents.
+ For every child in the graph, check if it comes after all of it's
+ parents.
"""
sort_result = topo_sort(graph)
iter_result = list(TopoSorter(graph).iter_topo_order())
for (node, parents) in graph:
for parent in parents:
- self.assertTrue(sort_result.index(node) > sort_result.index(parent),
- "parent %s must come before child %s:\n%s" % (parent, node, sort_result))
- self.assertTrue(iter_result.index(node) > iter_result.index(parent),
- "parent %s must come before child %s:\n%s" % (parent, node, iter_result))
+ if sort_result.index(node) < sort_result.index(parent):
+ self.fail("parent %s must come before child %s:\n%s"
+ % (parent, node, sort_result))
+ if iter_result.index(node) < iter_result.index(parent):
+ self.fail("parent %s must come before child %s:\n%s"
+ % (parent, node, iter_result))
def test_tsort_empty(self):
"""TopoSort empty list"""
More information about the bazaar-commits
mailing list