1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
import unittest
import pyanaconda.tsort
class TopologicalSortTestCase(unittest.TestCase):
def runTest(self):
items = [1, 2, 3, 4, 5]
edges = [(5, 4), (4, 3), (3, 2), (2, 1)]
graph = pyanaconda.tsort.create_graph(items, edges)
self._tsortTest(graph)
edges = [(5, 4), (2, 3), (1, 5)]
graph = pyanaconda.tsort.create_graph(items, edges)
self._tsortTest(graph)
edges = [(5, 4), (4, 3), (3, 2), (2, 1), (3, 5)]
graph = pyanaconda.tsort.create_graph(items, edges)
self.failUnlessRaises(pyanaconda.tsort.CyclicGraphError,
pyanaconda.tsort.tsort,
graph)
edges = [(5, 4), (4, 3), (3, 2), (2, 1), (2, 3)]
graph = pyanaconda.tsort.create_graph(items, edges)
self.failUnlessRaises(pyanaconda.tsort.CyclicGraphError,
pyanaconda.tsort.tsort,
graph)
items = ['a', 'b', 'c', 'd']
edges = [('a', 'c'), ('c', 'b')]
graph = pyanaconda.tsort.create_graph(items, edges)
self._tsortTest(graph)
def _tsortTest(self, graph):
def check_order(order, graph):
# since multiple solutions can potentially exist, just verify
# that the ordering constraints are satisfied
for parent, child in graph['edges']:
if order.index(parent) > order.index(child):
return False
return True
try:
order = pyanaconda.tsort.tsort(graph)
except Exception as e:
self.fail(e)
# verify output list is of the correct length
self.failIf(len(order) != len(graph['items']),
"sorted list length is incorrect")
# verify that all ordering constraints are satisfied
self.failUnless(check_order(order, graph),
"ordering constraints not satisfied")
def suite():
return unittest.TestLoader().loadTestsFromTestCase(TopologicalSortTestCase)
if __name__ == "__main__":
unittest.main()
|
