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
63
64
65
66
67
68
69
70
71
72
73
74
75
|
import unittest
from igraph import Graph, InternalError
def powerset(iterable):
items_powers = [(item, 1 << i) for i, item in enumerate(iterable)]
for i in range(1 << len(items_powers)):
for item, power in items_powers:
if i & power:
yield item
class IsSeparatorTests(unittest.TestCase):
def testIsSeparator(self):
g = Graph.Lattice([8, 4], circular=False)
self.assertTrue(g.is_separator([3, 11, 19, 27]))
self.assertFalse(g.is_separator([10, 11, 18, 19]))
self.assertTrue(g.is_separator([29, 20, 11, 2]))
self.assertTrue(g.is_separator([16, 25, 17]))
g = Graph.Lattice([8, 4], circular=True)
self.assertFalse(g.is_separator([3, 11, 19, 27]))
self.assertFalse(g.is_separator([29, 20, 11, 2]))
self.assertFalse(g.is_separator(list(range(32))))
self.assertRaises(InternalError, g.is_separator, list(range(33)))
def testIsMinimalSeparator(self):
g = Graph.Lattice([8, 4], circular=False)
self.assertTrue(g.is_minimal_separator([3, 11, 19, 27]))
self.assertFalse(g.is_minimal_separator([3, 11, 19, 27, 28]))
self.assertFalse(g.is_minimal_separator([16, 25, 17]))
self.assertTrue(g.is_minimal_separator([16, 25]))
self.assertFalse(g.is_minimal_separator(list(range(32))))
self.assertRaises(InternalError, g.is_minimal_separator, list(range(33)))
def testAllMinimalSTSeparators(self):
g = Graph.Famous("petersen")
min_st_seps = {tuple(x) for x in g.all_minimal_st_separators()}
for vs in powerset(list(range(g.vcount()))):
if vs in min_st_seps:
self.assertTrue(g.is_minimal_separator(vs))
else:
self.assertFalse(g.is_minimal_separator(vs))
def testMinimumSizeSeparators(self):
g = Graph.Famous("zachary")
min_st_seps = {tuple(x) for x in g.all_minimal_st_separators()}
min_size_seps = [tuple(x) for x in g.minimum_size_separators()]
self.assertTrue(set(min_size_seps).issubset(min_st_seps))
self.assertTrue(len(set(min_size_seps)) == len(min_size_seps))
size = len(min_size_seps[0])
self.assertTrue(len(s) != size for s in min_size_seps)
self.assertTrue(
sum(1 for s in min_st_seps if len(s) == size) == len(min_size_seps)
)
def suite():
is_separator_suite = unittest.defaultTestLoader.loadTestsFromTestCase(
IsSeparatorTests
)
return unittest.TestSuite([is_separator_suite])
def test():
runner = unittest.TextTestRunner()
runner.run(suite())
if __name__ == "__main__":
test()
|
