← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/selftest/testtsort.py

  • Committer: Robert Collins
  • Date: 2005-10-27 19:45:18 UTC
  • mfrom: (1185.16.130)
  • Revision ID: robertc@robertcollins.net-20051027194518-58afabc9ab280bb0
Merge from Martin

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/selftest/testtsort.py
 
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
 
 
17
"""Tests for topological sort.
 
18
"""
 
19
 
 
20
import os
 
21
import sys
 
22
 
 
23
from bzrlib.selftest import TestCase
 
24
from bzrlib.tsort import topo_sort
 
25
from bzrlib.errors import GraphCycleError
 
26
 
 
27
class TopoSortTests(TestCase):
 
28
 
 
29
    def test_tsort_empty(self):
 
30
        """TopoSort empty list"""
 
31
        self.assertEquals(topo_sort([]), [])
 
32
 
 
33
    def test_tsort_easy(self):
 
34
        """TopoSort list with one node"""
 
35
        self.assertEquals(topo_sort({0: []}.items()),
 
36
                          [0])
 
37
 
 
38
    def test_tsort_cycle(self):
 
39
        """TopoSort traps graph with cycles"""
 
40
        self.assertRaises(GraphCycleError,
 
41
                          topo_sort,
 
42
                          {0: [1], 
 
43
                           1: [0]}.iteritems())
 
44
 
 
45
    def test_tsort_cycle_2(self):
 
46
        """TopoSort traps graph with longer cycle"""
 
47
        self.assertRaises(GraphCycleError,
 
48
                          topo_sort,
 
49
                          {0: [1], 
 
50
                           1: [2], 
 
51
                           2: [0]}.iteritems())
 
52
                 
 
53
    def test_tsort_1(self):
 
54
        """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])
 
61
 
 
62
    def test_tsort_partial(self):
 
63
        """Topological sort with partial ordering.
 
64
 
 
65
        If the graph does not give an order between two nodes, they are 
 
66
        returned in lexicographical order.
 
67
        """
 
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, ])