|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
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 |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
25 |
from bzrlib.errors import GraphCycleError |
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
26 |
|
27 |
class TopoSortTests(TestCase): |
|
28 |
||
29 |
def test_tsort_empty(self): |
|
30 |
"""TopoSort empty list"""
|
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
31 |
self.assertEquals(topo_sort([]), []) |
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
32 |
|
33 |
def test_tsort_easy(self): |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
34 |
"""TopoSort list with one node"""
|
35 |
self.assertEquals(topo_sort({0: []}.items()), |
|
36 |
[0]) |
|
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
37 |
|
38 |
def test_tsort_cycle(self): |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
39 |
"""TopoSort traps graph with cycles"""
|
40 |
self.assertRaises(GraphCycleError, |
|
41 |
topo_sort, |
|
42 |
{0: [1], |
|
43 |
1: [0]}.iteritems()) |
|
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
44 |
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
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 |
||
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
53 |
def test_tsort_1(self): |
54 |
"""TopoSort simple nontrivial graph"""
|
|
|
1185.16.114
by mbp at sourcefrog
Improved topological sort |
55 |
self.assertEquals(topo_sort({0: [3], |
56 |
1: [4], |
|
57 |
2: [1, 4], |
|
58 |
3: [], |
|
59 |
4: [0, 3]}.iteritems()), |
|
|
1185.16.113
by mbp at sourcefrog
Add topo_sort utility function |
60 |
[3, 0, 4, 1, 2]) |
|
1185.16.115
by mbp at sourcefrog
Another topo_sort test |
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, ]) |