← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-08-19 18:04:49 UTC
  • mfrom: (4593.5.43 1.19-known-graph-sorted)
  • Revision ID: pqm@pqm.ubuntu.com-20090819180449-p5dibldf9pcp24n4
(jam) Add VersionedFiles.get_known_graph_ancestry and
        KnownGraph.merge_sort()

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,