/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

  • Committer: Robert Collins
  • Date: 2009-08-25 19:29:41 UTC
  • mfrom: (4648 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4649.
  • Revision ID: robertc@robertcollins.net-20090825192941-x2kg9ikhsapjbs7b
Merge bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_tsort.py
17
17
 
18
18
"""Tests for topological sort."""
19
19
 
 
20
import pprint
20
21
 
21
22
from bzrlib.tests import TestCase
22
23
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
39
40
                          list,
40
41
                          TopoSorter(graph).iter_topo_order())
41
42
 
 
43
    def assertSortAndIterateOrder(self, graph):
 
44
        """Check topo_sort and iter_topo_order is genuinely topological order.
 
45
 
 
46
        For every child in the graph, check if it comes after all of it's
 
47
        parents.
 
48
        """
 
49
        sort_result = topo_sort(graph)
 
50
        iter_result = list(TopoSorter(graph).iter_topo_order())
 
51
        for (node, parents) in graph:
 
52
            for parent in parents:
 
53
                if sort_result.index(node) < sort_result.index(parent):
 
54
                    self.fail("parent %s must come before child %s:\n%s"
 
55
                              % (parent, node, sort_result))
 
56
                if iter_result.index(node) < iter_result.index(parent):
 
57
                    self.fail("parent %s must come before child %s:\n%s"
 
58
                              % (parent, node, iter_result))
 
59
 
42
60
    def test_tsort_empty(self):
43
61
        """TopoSort empty list"""
44
62
        self.assertSortAndIterate([], [])
60
78
                                        1: [2],
61
79
                                        2: [0]}.items())
62
80
 
 
81
    def test_topo_sort_cycle_with_tail(self):
 
82
        """TopoSort traps graph with longer cycle"""
 
83
        self.assertSortAndIterateRaise(GraphCycleError,
 
84
                                       {0: [1],
 
85
                                        1: [2],
 
86
                                        2: [3, 4],
 
87
                                        3: [0],
 
88
                                        4: []}.items())
 
89
 
63
90
    def test_tsort_1(self):
64
91
        """TopoSort simple nontrivial graph"""
65
92
        self.assertSortAndIterate({0: [3],
72
99
    def test_tsort_partial(self):
73
100
        """Topological sort with partial ordering.
74
101
 
75
 
        If the graph does not give an order between two nodes, they are
76
 
        returned in lexicographical order.
 
102
        Multiple correct orderings are possible, so test for 
 
103
        correctness, not for exact match on the resulting list.
77
104
        """
78
 
        self.assertSortAndIterate(([(0, []),
 
105
        self.assertSortAndIterateOrder([(0, []),
79
106
                                   (1, [0]),
80
107
                                   (2, [0]),
81
108
                                   (3, [0]),
83
110
                                   (5, [1, 2]),
84
111
                                   (6, [1, 2]),
85
112
                                   (7, [2, 3]),
86
 
                                   (8, [0, 1, 4, 5, 6])]),
87
 
                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])
 
113
                                   (8, [0, 1, 4, 5, 6])])
88
114
 
89
115
    def test_tsort_unincluded_parent(self):
90
116
        """Sort nodes, but don't include some parents in the output"""
102
128
                           mainline_revisions=mainline_revisions,
103
129
                           generate_revno=generate_revno)
104
130
        if result_list != value:
105
 
            import pprint
106
131
            self.assertEqualDiff(pprint.pformat(result_list),
107
132
                                 pprint.pformat(value))
108
 
        self.assertEquals(result_list,
109
 
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions,
110
 
                generate_revno=generate_revno))
111
133
        self.assertEqual(result_list,
112
134
            list(MergeSorter(
113
135
                graph,
211
233
        self.assertSortAndIterate(graph, 'F',
212
234
            [(0, 'F', 0, (3,), False),
213
235
             (1, 'D', 1, (2,2,1), False),
214
 
             (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
 
236
             (2, 'C', 2, (2,1,1), True),
215
237
             (3, 'B', 0, (2,), False),
216
238
             (4, 'A', 0, (1,), True),
217
239
             ], True)