« back to all changes in this revision
Viewing changes to bzrlib/tests/test_tsort.py
- browse files at revision 1570.1.7
- compare with another revision
- compare with revision 1226
- download diff
- download tarball
- view history from revision 1570.1.7
- Committer: Robert Collins
- Date: 2006-02-24 23:13:20 UTC
- mto: (1587.1.1 integration)
- mto: This revision was merged to the branch mainline in revision 1588.
- Revision ID: robertc@robertcollins.net-20060224231320-dbaf879d3070bfd7
Replace the slow topo_sort routine with a much faster one for non trivial datasets.
added
removed
bzrlib/tests/test_tsort.py
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
16
17
17
18
"""Tests for topological sort."""
18
19
19
20
20
from bzrlib.reconcile import topological_sort
21
21
from bzrlib.tests import TestCase
22
from bzrlib.tsort import topo_sort
22
from bzrlib.tsort import topo_sort, TopoSorter
23
23
from bzrlib.errors import GraphCycleError
24
24
25
25
26
26
class TopoSortTests(TestCase):
27
27
28
def assertSortAndIterate(self, graph, result_list):
29
"""Check that sorting and iter_topo_order on graph works."""
30
self.assertEquals(result_list, topo_sort(graph))
31
self.assertEqual(result_list,
32
list(TopoSorter(graph).iter_topo_order()))
33
34
def assertSortAndIterateRaise(self, exception_type, graph):
35
"""Try both iterating and topo_sorting graph and expect an exception."""
36
self.assertRaises(exception_type, topo_sort, graph)
37
self.assertRaises(exception_type,
38
list,
39
TopoSorter(graph).iter_topo_order())
40
28
41
def test_tsort_empty(self):
29
42
"""TopoSort empty list"""
30
self.assertEquals(topo_sort([]), [])
43
self.assertSortAndIterate([], [])
31
44
32
45
def test_tsort_easy(self):
33
46
"""TopoSort list with one node"""
34
self.assertEquals(topo_sort({0: []}.items()),
35
[0])
47
self.assertSortAndIterate({0: []}.items(), [0])
36
48
37
49
def test_tsort_cycle(self):
38
50
"""TopoSort traps graph with cycles"""
39
self.assertRaises(GraphCycleError,
40
topo_sort,
41
{0: [1],
42
1: [0]}.iteritems())
51
self.assertSortAndIterateRaise(GraphCycleError,
52
{0: [1],
53
1: [0]}.items())
43
54
44
55
def test_tsort_cycle_2(self):
45
56
"""TopoSort traps graph with longer cycle"""
46
self.assertRaises(GraphCycleError,
47
topo_sort,
48
{0: [1],
49
1: [2],
50
2: [0]}.iteritems())
57
self.assertSortAndIterateRaise(GraphCycleError,
58
{0: [1],
59
1: [2],
60
2: [0]}.items())
51
61
52
62
def test_tsort_1(self):
53
63
"""TopoSort simple nontrivial graph"""
54
self.assertEquals(topo_sort({0: [3],
55
1: [4],
56
2: [1, 4],
57
3: [],
58
4: [0, 3]}.iteritems()),
59
[3, 0, 4, 1, 2])
64
self.assertSortAndIterate({0: [3],
65
1: [4],
66
2: [1, 4],
67
3: [],
68
4: [0, 3]}.items(),
69
[3, 0, 4, 1, 2])
60
70
61
71
def test_tsort_partial(self):
62
72
"""Topological sort with partial ordering.
64
74
If the graph does not give an order between two nodes, they are
65
75
returned in lexicographical order.
66
76
"""
67
self.assertEquals(topo_sort([(0, []),
68
(1, [0]),
69
(2, [0]),
70
(3, [0]),
71
(4, [1, 2, 3]),
72
(5, [1, 2]),
73
(6, [1, 2]),
74
(7, [2, 3]),
75
(8, [0, 1, 4, 5, 6])]),
76
[0, 1, 2, 3, 4, 5, 6, 7, 8, ])
77
78
def test_new_tsort_empty(self):
79
"""TopoSort empty list"""
80
self.assertEquals(topological_sort([]), [])
81
82
def test_new_tsort_easy(self):
83
"""TopoSort list with one node"""
84
self.assertEquals(topological_sort({0: []}.items()),
85
[0])
86
87
def test_new_tsort_cycle(self):
88
"""TopoSort traps graph with cycles"""
89
self.assertRaises(GraphCycleError,
90
topological_sort,
91
{0: [1],
92
1: [0]}.iteritems())
93
94
def test_new_tsort_cycle_2(self):
95
"""TopoSort traps graph with longer cycle"""
96
self.assertRaises(GraphCycleError,
97
topological_sort,
98
{0: [1],
99
1: [2],
100
2: [0]}.iteritems())
101
102
def test_new_tsort_1(self):
103
"""TopoSort simple nontrivial graph"""
104
self.assertEquals(topological_sort({0: [3],
105
1: [4],
106
2: [1, 4],
107
3: [],
108
4: [0, 3]}.iteritems()),
109
[3, 0, 4, 1, 2])
110
111
def test_new_tsort_partial(self):
112
"""Topological sort with partial ordering.
113
114
If the graph does not give an order between two nodes, they are
115
returned in lexicographical order.
116
"""
117
self.assertEquals(topological_sort([(0, []),
118
(1, [0]),
119
(2, [0]),
120
(3, [0]),
121
(4, [1, 2, 3]),
122
(5, [1, 2]),
123
(6, [1, 2]),
124
(7, [2, 3]),
125
(8, [0, 1, 4, 5, 6])]),
126
[0, 1, 2, 3, 4, 5, 6, 7, 8, ])
77
self.assertSortAndIterate(([(0, []),
78
(1, [0]),
79
(2, [0]),
80
(3, [0]),
81
(4, [1, 2, 3]),
82
(5, [1, 2]),
83
(6, [1, 2]),
84
(7, [2, 3]),
85
(8, [0, 1, 4, 5, 6])]),
86
[0, 1, 2, 3, 4, 5, 6, 7, 8])
Loggerhead is a web-based interface for Breezy
Version: 2.0.1