← 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: Robert Collins
  • Date: 2006-02-24 13:32:45 UTC
  • mto: (1587.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 1588.
  • Revision ID: robertc@robertcollins.net-20060224133245-7a448981e53b91f4
Update fast topological_sort to be a function and to have the topo_sort tests run against it.

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
22
 
 
 
17
"""Tests for topological sort."""
 
18
 
 
19
 
 
20
from bzrlib.reconcile import topological_sort
23
21
from bzrlib.tests import TestCase
24
22
from bzrlib.tsort import topo_sort
25
23
from bzrlib.errors import GraphCycleError
26
24
 
 
25
 
27
26
class TopoSortTests(TestCase):
28
27
 
29
28
    def test_tsort_empty(self):
75
74
                                    (7, [2, 3]),
76
75
                                    (8, [0, 1, 4, 5, 6])]),
77
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, ])