← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

Merge in upstream.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 
"""Tests for topological sort.
18
 
"""
19
 
 
20
 
import os
21
 
import sys
 
17
 
 
18
"""Tests for topological sort."""
 
19
 
22
20
 
23
21
from bzrlib.tests import TestCase
24
 
from bzrlib.tsort import topo_sort
 
22
from bzrlib.tsort import topo_sort, TopoSorter
25
23
from bzrlib.errors import GraphCycleError
26
24
 
 
25
 
27
26
class TopoSortTests(TestCase):
28
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
 
29
41
    def test_tsort_empty(self):
30
42
        """TopoSort empty list"""
31
 
        self.assertEquals(topo_sort([]), [])
 
43
        self.assertSortAndIterate([], [])
32
44
 
33
45
    def test_tsort_easy(self):
34
46
        """TopoSort list with one node"""
35
 
        self.assertEquals(topo_sort({0: []}.items()),
36
 
                          [0])
 
47
        self.assertSortAndIterate({0: []}.items(), [0])
37
48
 
38
49
    def test_tsort_cycle(self):
39
50
        """TopoSort traps graph with cycles"""
40
 
        self.assertRaises(GraphCycleError,
41
 
                          topo_sort,
42
 
                          {0: [1], 
43
 
                           1: [0]}.iteritems())
 
51
        self.assertSortAndIterateRaise(GraphCycleError,
 
52
                                       {0: [1], 
 
53
                                        1: [0]}.items())
44
54
 
45
55
    def test_tsort_cycle_2(self):
46
56
        """TopoSort traps graph with longer cycle"""
47
 
        self.assertRaises(GraphCycleError,
48
 
                          topo_sort,
49
 
                          {0: [1], 
50
 
                           1: [2], 
51
 
                           2: [0]}.iteritems())
 
57
        self.assertSortAndIterateRaise(GraphCycleError,
 
58
                                       {0: [1], 
 
59
                                        1: [2], 
 
60
                                        2: [0]}.items())
52
61
                 
53
62
    def test_tsort_1(self):
54
63
        """TopoSort simple nontrivial graph"""
55
 
        self.assertEquals(topo_sort({0: [3], 
56
 
                                     1: [4],
57
 
                                     2: [1, 4],
58
 
                                     3: [], 
59
 
                                     4: [0, 3]}.iteritems()),
60
 
                          [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])
61
70
 
62
71
    def test_tsort_partial(self):
63
72
        """Topological sort with partial ordering.
65
74
        If the graph does not give an order between two nodes, they are 
66
75
        returned in lexicographical order.
67
76
        """
68
 
        self.assertEquals(topo_sort([(0, []),
69
 
                                    (1, [0]),
70
 
                                    (2, [0]),
71
 
                                    (3, [0]),
72
 
                                    (4, [1, 2, 3]),
73
 
                                    (5, [1, 2]),
74
 
                                    (6, [1, 2]),
75
 
                                    (7, [2, 3]),
76
 
                                    (8, [0, 1, 4, 5, 6])]),
77
 
                          [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])