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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
import random
import unittest
from igraph import Graph, InternalError
class RandomWalkTests(unittest.TestCase):
def setUp(self):
random.seed(42)
def validate_walk(self, g, walk, start, length, mode="out"):
self.assertEqual(len(walk), length + 1)
prev = None
for vertex in walk:
if prev is not None:
self.assertTrue(vertex in g.neighbors(prev, mode=mode))
else:
self.assertEqual(start, vertex)
prev = vertex
def validate_edge_walk(self, g, walk, start, length, mode="out"):
self.assertEqual(len(walk), length)
prev_vertices = None
for edgeid in walk:
vertices = g.es[edgeid].tuple
if prev_vertices is not None:
self.assertTrue(
vertices[0] in prev_vertices or vertices[1] in prev_vertices
)
else:
self.assertTrue(start in vertices)
prev_vertices = vertices
def testRandomWalkUndirected(self):
g = Graph.GRG(100, 0.2)
for _i in range(100):
start = random.randint(0, g.vcount() - 1)
length = random.randint(0, 10)
walk = g.random_walk(start, length)
self.validate_walk(g, walk, start, length)
def testRandomWalkDirectedOut(self):
g = Graph.Tree(121, 3, mode="out")
mode = "out"
for _i in range(100):
start = 0
length = random.randint(0, 4)
walk = g.random_walk(start, length, mode)
self.validate_walk(g, walk, start, length, mode)
def testRandomWalkDirectedIn(self):
g = Graph.Tree(121, 3, mode="out")
mode = "in"
for _i in range(100):
start = random.randint(40, g.vcount() - 1)
length = random.randint(0, 4)
walk = g.random_walk(start, length, mode)
self.validate_walk(g, walk, start, length, mode)
def testRandomWalkDirectedAll(self):
g = Graph.Tree(121, 3, mode="out")
mode = "all"
for _i in range(100):
start = random.randint(0, g.vcount() - 1)
length = random.randint(0, 10)
walk = g.random_walk(start, length, mode)
self.validate_walk(g, walk, start, length, mode)
def testRandomWalkStuck(self):
g = Graph.Ring(10, circular=False, directed=True)
walk = g.random_walk(5, 20)
self.assertEqual([5, 6, 7, 8, 9], walk)
self.assertRaises(InternalError, g.random_walk, 5, 20, stuck="error")
def testRandomWalkUndirectedVertices(self):
g = Graph.GRG(100, 0.2)
for _i in range(10):
start = random.randint(0, g.vcount() - 1)
length = random.randint(0, 10)
walk = g.random_walk(start, length, return_type="vertices")
self.validate_walk(g, walk, start, length)
def testRandomWalkUndirectedEdges(self):
g = Graph.GRG(100, 0.2)
for _i in range(10):
start = random.randint(0, g.vcount() - 1)
length = random.randint(0, 10)
walk = g.random_walk(start, length, return_type="edges")
self.validate_edge_walk(g, walk, start, length)
def testRandomWalkUndirectedBoth(self):
g = Graph.GRG(100, 0.2)
for _i in range(10):
start = random.randint(0, g.vcount() - 1)
length = random.randint(0, 10)
walk_dic = g.random_walk(start, length, return_type="both")
self.assertTrue("vertices" in walk_dic)
self.assertTrue("edges" in walk_dic)
self.validate_edge_walk(g, walk_dic["edges"], start, length)
self.validate_walk(g, walk_dic["vertices"], start, length)
def testRandomWalkUndirectedWeighted(self):
g = Graph.GRG(100, 0.2)
g.es["weight"] = [1.0 for i in range(g.ecount())]
for _i in range(100):
start = random.randint(0, g.vcount() - 1)
length = random.randint(0, 10)
walk = g.random_walk(start, length, weights="weight")
self.validate_walk(g, walk, start, length)
def suite():
random_walk_suite = unittest.defaultTestLoader.loadTestsFromTestCase(
RandomWalkTests
)
return unittest.TestSuite([random_walk_suite])
def test():
runner = unittest.TextTestRunner()
runner.run(suite())
if __name__ == "__main__":
test()
|
