|
1 #!/usr/bin/python |
|
2 |
|
3 # Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com> |
|
4 # |
|
5 # Permission is hereby granted, free of charge, to any person |
|
6 # obtaining a copy of this software and associated documentation |
|
7 # files (the "Software"), to deal in the Software without |
|
8 # restriction, including without limitation the rights to use, |
|
9 # copy, modify, merge, publish, distribute, sublicense, and/or sell |
|
10 # copies of the Software, and to permit persons to whom the |
|
11 # Software is furnished to do so, subject to the following |
|
12 # conditions: |
|
13 |
|
14 # The above copyright notice and this permission notice shall be |
|
15 # included in all copies or substantial portions of the Software. |
|
16 |
|
17 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
18 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
|
19 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
|
20 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
|
21 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
|
22 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
|
23 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
24 # OTHER DEALINGS IN THE SOFTWARE. |
|
25 |
|
26 |
|
27 """ |
|
28 python-graph |
|
29 |
|
30 Unit tests for python-graph |
|
31 """ |
|
32 |
|
33 |
|
34 # Imports |
|
35 import sys |
|
36 sys.path.append('..') |
|
37 import copy |
|
38 import graph |
|
39 import unittest |
|
40 |
|
41 |
|
42 # Tests |
|
43 class testGraph(unittest.TestCase): |
|
44 |
|
45 def setUp(self): |
|
46 pass |
|
47 |
|
48 def testRandomGraph(self): |
|
49 gr = graph.graph() |
|
50 gr.generate(100, 500) |
|
51 self.assertEqual(gr.nodes(),range(100)) |
|
52 self.assertEqual(len(gr.edges()), 500*2) |
|
53 for each, other in gr.edges(): |
|
54 self.assertTrue(each in gr) |
|
55 self.assertTrue(other in gr) |
|
56 |
|
57 def testRandomEmptyGraph(self): |
|
58 gr = graph.graph() |
|
59 gr.generate(0,0) |
|
60 self.assertTrue(gr.nodes() == []) |
|
61 self.assertTrue(gr.edges() == []) |
|
62 |
|
63 def testNodeRemoval(self): |
|
64 gr = graph.graph() |
|
65 gr.generate(10, 30) |
|
66 gr.del_node(0) |
|
67 self.assertTrue(0 not in gr) |
|
68 for each, other in gr.edges(): |
|
69 self.assertTrue(each in gr) |
|
70 self.assertTrue(other in gr) |
|
71 |
|
72 def testGraphInverse(self): |
|
73 gr = graph.graph() |
|
74 gr.generate(50, 300) |
|
75 inv = gr.inverse() |
|
76 for each in gr.edges(): |
|
77 self.assertTrue(each not in inv.edges()) |
|
78 for each in inv.edges(): |
|
79 self.assertTrue(each not in gr.edges()) |
|
80 |
|
81 def testEmptyGraphInverse(self): |
|
82 gr = graph.graph() |
|
83 inv = gr.inverse() |
|
84 self.assertTrue(gr.nodes() == []) |
|
85 self.assertTrue(gr.edges() == []) |
|
86 |
|
87 def testGraphComplete(self): |
|
88 gr = graph.graph() |
|
89 gr.add_nodes(xrange(10)) |
|
90 gr.complete() |
|
91 for i in xrange(10): |
|
92 for j in range(10): |
|
93 self.assertTrue((i, j) in gr.edges() or i == j) |
|
94 |
|
95 def testEmptyGraphComplete(self): |
|
96 gr = graph.graph() |
|
97 gr.complete() |
|
98 self.assertTrue(gr.nodes() == []) |
|
99 self.assertTrue(gr.edges() == []) |
|
100 |
|
101 def testGraphWithOneNodeComplete(self): |
|
102 gr = graph.graph() |
|
103 gr.add_node(0) |
|
104 gr.complete() |
|
105 self.assertTrue(gr.nodes() == [0]) |
|
106 self.assertTrue(gr.edges() == []) |
|
107 |
|
108 def testAddGraph(self): |
|
109 gr1 = graph.graph() |
|
110 gr1.generate(25, 100) |
|
111 gr2 = graph.graph() |
|
112 gr2.generate(40, 200) |
|
113 gr1.add_graph(gr2) |
|
114 for each in gr2.nodes(): |
|
115 self.assertTrue(each in gr1) |
|
116 for each in gr2.edges(): |
|
117 self.assertTrue(each in gr1.edges()) |
|
118 |
|
119 def testAddEmptyGraph(self): |
|
120 gr1 = graph.graph() |
|
121 gr1.generate(25, 100) |
|
122 gr1c = copy.copy(gr1) |
|
123 gr2 = graph.graph() |
|
124 gr1.add_graph(gr2) |
|
125 self.assertTrue(gr1.nodes() == gr1c.nodes()) |
|
126 self.assertTrue(gr1.edges() == gr1c.edges()) |
|
127 |
|
128 def testAddSpanningTree(self): |
|
129 gr = graph.graph() |
|
130 st = {0: None, 1: 0, 2:0, 3: 1, 4: 2, 5: 3} |
|
131 gr.add_spanning_tree(st) |
|
132 for each in st: |
|
133 self.assertTrue((each, st[each]) in gr.edges() or (each, st[each]) == (0, None)) |
|
134 self.assertTrue((st[each], each) in gr.edges() or (each, st[each]) == (0, None)) |
|
135 |
|
136 def testAddEmptySpanningTree(self): |
|
137 gr = graph.graph() |
|
138 st = {} |
|
139 gr.add_spanning_tree(st) |
|
140 self.assertTrue(gr.nodes() == []) |
|
141 self.assertTrue(gr.edges() == []) |
|
142 |
|
143 |
|
144 # Run tests |
|
145 if __name__ == '__main__': |
|
146 unittest.main() |