bzr branch
http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
1 |
# Copyright (C) 2005 by 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
16 |
||
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
17 |
|
|
1570.1.6
by Robert Collins
Update fast topological_sort to be a function and to have the topo_sort tests run against it. |
18 |
"""Tests for topological sort."""
|
19 |
||
20 |
||
|
1185.31.25
by John Arbash Meinel
Renamed all of the tests from selftest/foo.py to tests/test_foo.py |
21 |
from bzrlib.tests import TestCase |
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
22 |
from bzrlib.tsort import topo_sort, TopoSorter |
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
23 |
from bzrlib.errors import GraphCycleError |
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
24 |
|
|
1570.1.6
by Robert Collins
Update fast topological_sort to be a function and to have the topo_sort tests run against it. |
25 |
|
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
26 |
class TopoSortTests(TestCase): |
27 |
||
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
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 |
||
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
41 |
def test_tsort_empty(self): |
42 |
"""TopoSort empty list""" |
|
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
43 |
self.assertSortAndIterate([], []) |
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
44 |
|
45 |
def test_tsort_easy(self): |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
46 |
"""TopoSort list with one node""" |
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
47 |
self.assertSortAndIterate({0: []}.items(), [0]) |
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
48 |
|
49 |
def test_tsort_cycle(self): |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
50 |
"""TopoSort traps graph with cycles""" |
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
51 |
self.assertSortAndIterateRaise(GraphCycleError, |
52 |
{0: [1], |
|
53 |
1: [0]}.items()) |
|
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
54 |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
55 |
def test_tsort_cycle_2(self): |
56 |
"""TopoSort traps graph with longer cycle""" |
|
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
57 |
self.assertSortAndIterateRaise(GraphCycleError, |
58 |
{0: [1], |
|
59 |
1: [2], |
|
60 |
2: [0]}.items()) |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
61 |
|
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
62 |
def test_tsort_1(self): |
63 |
"""TopoSort simple nontrivial graph""" |
|
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
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]) |
|
|
1185.16.115
by mbp at sourcefrog
Another topo_sort test |
70 |
|
71 |
def test_tsort_partial(self): |
|
72 |
"""Topological sort with partial ordering. |
|
73 |
||
74 |
If the graph does not give an order between two nodes, they are
|
|
75 |
returned in lexicographical order.
|
|
76 |
"""
|
|
|
1570.1.7
by Robert Collins
Replace the slow topo_sort routine with a much faster one for non trivial datasets. |
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]) |