ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tests / test_cycles.py @ 5cef0f13
History  View  Annotate  Download (11.4 KB)
1 
#!/usr/bin/env python


2 
from nose.tools import * 
3 
import networkx 
4 
import networkx as nx 
5  
6 
from networkx.algorithms import find_cycle 
7 
from networkx.algorithms import minimum_cycle_basis 
8  
9 
FORWARD = nx.algorithms.edgedfs.FORWARD 
10 
REVERSE = nx.algorithms.edgedfs.REVERSE 
11  
12  
13 
class TestCycles: 
14 
def setUp(self): 
15 
G = networkx.Graph() 
16 
nx.add_cycle(G, [0, 1, 2, 3]) 
17 
nx.add_cycle(G, [0, 3, 4, 5]) 
18 
nx.add_cycle(G, [0, 1, 6, 7, 8]) 
19 
G.add_edge(8, 9) 
20 
self.G = G

21  
22 
def is_cyclic_permutation(self, a, b): 
23 
n = len(a)

24 
if len(b) != n: 
25 
return False 
26 
l = a + a 
27 
return any(l[i:i + n] == b for i in range(n)) 
28  
29 
def test_cycle_basis(self): 
30 
G = self.G

31 
cy = networkx.cycle_basis(G, 0)

32 
sort_cy = sorted(sorted(c) for c in cy) 
33 
assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]) 
34 
cy = networkx.cycle_basis(G, 1)

35 
sort_cy = sorted(sorted(c) for c in cy) 
36 
assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]) 
37 
cy = networkx.cycle_basis(G, 9)

38 
sort_cy = sorted(sorted(c) for c in cy) 
39 
assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]) 
40 
# test disconnected graphs

41 
nx.add_cycle(G, "ABC")

42 
cy = networkx.cycle_basis(G, 9)

43 
sort_cy = sorted(sorted(c) for c in cy[:1]) + [sorted(cy[1])] 
44 
assert_equal(sort_cy, [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5], 
45 
['A', 'B', 'C']]) 
46  
47 
@raises(nx.NetworkXNotImplemented)

48 
def test_cycle_basis(self): 
49 
G = nx.DiGraph() 
50 
cy = networkx.cycle_basis(G, 0)

51  
52 
@raises(nx.NetworkXNotImplemented)

53 
def test_cycle_basis(self): 
54 
G = nx.MultiGraph() 
55 
cy = networkx.cycle_basis(G, 0)

56  
57 
def test_simple_cycles(self): 
58 
edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)] 
59 
G = nx.DiGraph(edges) 
60 
cc = sorted(nx.simple_cycles(G))

61 
ca = [[0], [0, 1, 2], [0, 2], [1, 2], [2]] 
62 
assert_equal(len(cc), len(ca)) 
63 
for c in cc: 
64 
assert_true(any(self.is_cyclic_permutation(c, rc) for rc in ca)) 
65  
66 
@raises(nx.NetworkXNotImplemented)

67 
def test_simple_cycles_graph(self): 
68 
G = nx.Graph() 
69 
c = sorted(nx.simple_cycles(G))

70  
71 
def test_unsortable(self): 
72 
# TODO What does this test do? das 6/2013

73 
G = nx.DiGraph() 
74 
nx.add_cycle(G, ['a', 1]) 
75 
c = list(nx.simple_cycles(G))

76  
77 
def test_simple_cycles_small(self): 
78 
G = nx.DiGraph() 
79 
nx.add_cycle(G, [1, 2, 3]) 
80 
c = sorted(nx.simple_cycles(G))

81 
assert_equal(len(c), 1) 
82 
assert_true(self.is_cyclic_permutation(c[0], [1, 2, 3])) 
83 
nx.add_cycle(G, [10, 20, 30]) 
84 
cc = sorted(nx.simple_cycles(G))

85 
assert_equal(len(cc), 2) 
86 
ca = [[1, 2, 3], [10, 20, 30]] 
87 
for c in cc: 
88 
assert_true(any(self.is_cyclic_permutation(c, rc) for rc in ca)) 
89  
90 
def test_simple_cycles_empty(self): 
91 
G = nx.DiGraph() 
92 
assert_equal(list(nx.simple_cycles(G)), [])

93  
94 
def test_complete_directed_graph(self): 
95 
# see table 2 in Johnson's paper

96 
ncircuits = [1, 5, 20, 84, 409, 2365, 16064] 
97 
for n, c in zip(range(2, 9), ncircuits): 
98 
G = nx.DiGraph(nx.complete_graph(n)) 
99 
assert_equal(len(list(nx.simple_cycles(G))), c) 
100  
101 
def worst_case_graph(self, k): 
102 
# see figure 1 in Johnson's paper

103 
# this graph has exactly 3k simple cycles

104 
G = nx.DiGraph() 
105 
for n in range(2, k + 2): 
106 
G.add_edge(1, n)

107 
G.add_edge(n, k + 2)

108 
G.add_edge(2 * k + 1, 1) 
109 
for n in range(k + 2, 2 * k + 2): 
110 
G.add_edge(n, 2 * k + 2) 
111 
G.add_edge(n, n + 1)

112 
G.add_edge(2 * k + 3, k + 2) 
113 
for n in range(2 * k + 3, 3 * k + 3): 
114 
G.add_edge(2 * k + 2, n) 
115 
G.add_edge(n, 3 * k + 3) 
116 
G.add_edge(3 * k + 3, 2 * k + 2) 
117 
return G

118  
119 
def test_worst_case_graph(self): 
120 
# see figure 1 in Johnson's paper

121 
for k in range(3, 10): 
122 
G = self.worst_case_graph(k)

123 
l = len(list(nx.simple_cycles(G))) 
124 
assert_equal(l, 3 * k)

125  
126 
def test_recursive_simple_and_not(self): 
127 
for k in range(2, 10): 
128 
G = self.worst_case_graph(k)

129 
cc = sorted(nx.simple_cycles(G))

130 
rcc = sorted(nx.recursive_simple_cycles(G))

131 
assert_equal(len(cc), len(rcc)) 
132 
for c in cc: 
133 
assert_true(any(self.is_cyclic_permutation(c, r) for r in rcc)) 
134 
for rc in rcc: 
135 
assert_true(any(self.is_cyclic_permutation(rc, c) for c in cc)) 
136  
137 
def test_simple_graph_with_reported_bug(self): 
138 
G = nx.DiGraph() 
139 
edges = [(0, 2), (0, 3), (1, 0), (1, 3), (2, 1), (2, 4), 
140 
(3, 2), (3, 4), (4, 0), (4, 1), (4, 5), (5, 0), 
141 
(5, 1), (5, 2), (5, 3)] 
142 
G.add_edges_from(edges) 
143 
cc = sorted(nx.simple_cycles(G))

144 
assert_equal(len(cc), 26) 
145 
rcc = sorted(nx.recursive_simple_cycles(G))

146 
assert_equal(len(cc), len(rcc)) 
147 
for c in cc: 
148 
assert_true(any(self.is_cyclic_permutation(c, rc) for rc in rcc)) 
149 
for rc in rcc: 
150 
assert_true(any(self.is_cyclic_permutation(rc, c) for c in cc)) 
151  
152 
# These tests might fail with hash randomization since they depend on

153 
# edge_dfs. For more information, see the comments in:

154 
# networkx/algorithms/traversal/tests/test_edgedfs.py

155  
156  
157 
class TestFindCycle(object): 
158 
def setUp(self): 
159 
self.nodes = [0, 1, 2, 3] 
160 
self.edges = [(1, 0), (0, 1), (1, 0), (1, 0), (2, 1), (3, 1)] 
161  
162 
def test_graph_nocycle(self): 
163 
G = nx.Graph(self.edges)

164 
assert_raises(nx.exception.NetworkXNoCycle, find_cycle, G, self.nodes)

165  
166 
def test_graph_cycle(self): 
167 
G = nx.Graph(self.edges)

168 
G.add_edge(2, 0) 
169 
x = list(find_cycle(G, self.nodes)) 
170 
x_ = [(0, 1), (1, 2), (2, 0)] 
171 
assert_equal(x, x_) 
172  
173 
def test_graph_orientation_none(self): 
174 
G = nx.Graph(self.edges)

175 
G.add_edge(2, 0) 
176 
x = list(find_cycle(G, self.nodes, orientation=None)) 
177 
x_ = [(0, 1), (1, 2), (2, 0)] 
178 
assert_equal(x, x_) 
179  
180 
def test_graph_orientation_original(self): 
181 
G = nx.Graph(self.edges)

182 
G.add_edge(2, 0) 
183 
x = list(find_cycle(G, self.nodes, orientation='original')) 
184 
x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 0, FORWARD)] 
185 
assert_equal(x, x_) 
186  
187 
def test_digraph(self): 
188 
G = nx.DiGraph(self.edges)

189 
x = list(find_cycle(G, self.nodes)) 
190 
x_ = [(0, 1), (1, 0)] 
191 
assert_equal(x, x_) 
192  
193 
def test_digraph_orientation_none(self): 
194 
G = nx.DiGraph(self.edges)

195 
x = list(find_cycle(G, self.nodes, orientation=None)) 
196 
x_ = [(0, 1), (1, 0)] 
197 
assert_equal(x, x_) 
198  
199 
def test_digraph_orientation_original(self): 
200 
G = nx.DiGraph(self.edges)

201 
x = list(find_cycle(G, self.nodes, orientation='original')) 
202 
x_ = [(0, 1, FORWARD), (1, 0, FORWARD)] 
203 
assert_equal(x, x_) 
204  
205 
def test_multigraph(self): 
206 
G = nx.MultiGraph(self.edges)

207 
x = list(find_cycle(G, self.nodes)) 
208 
x_ = [(0, 1, 0), (1, 0, 1)] # or (1, 0, 2) 
209 
# Hash randomization...could be any edge.

210 
assert_equal(x[0], x_[0]) 
211 
assert_equal(x[1][:2], x_[1][:2]) 
212  
213 
def test_multidigraph(self): 
214 
G = nx.MultiDiGraph(self.edges)

215 
x = list(find_cycle(G, self.nodes)) 
216 
x_ = [(0, 1, 0), (1, 0, 0)] # (1, 0, 1) 
217 
assert_equal(x[0], x_[0]) 
218 
assert_equal(x[1][:2], x_[1][:2]) 
219  
220 
def test_digraph_ignore(self): 
221 
G = nx.DiGraph(self.edges)

222 
x = list(find_cycle(G, self.nodes, orientation='ignore')) 
223 
x_ = [(0, 1, FORWARD), (1, 0, FORWARD)] 
224 
assert_equal(x, x_) 
225  
226 
def test_digraph_reverse(self): 
227 
G = nx.DiGraph(self.edges)

228 
x = list(find_cycle(G, self.nodes, orientation='reverse')) 
229 
x_ = [(1, 0, REVERSE), (0, 1, REVERSE)] 
230 
assert_equal(x, x_) 
231  
232 
def test_multidigraph_ignore(self): 
233 
G = nx.MultiDiGraph(self.edges)

234 
x = list(find_cycle(G, self.nodes, orientation='ignore')) 
235 
x_ = [(0, 1, 0, FORWARD), (1, 0, 0, FORWARD)] # or (1, 0, 1, 1) 
236 
assert_equal(x[0], x_[0]) 
237 
assert_equal(x[1][:2], x_[1][:2]) 
238 
assert_equal(x[1][3], x_[1][3]) 
239  
240 
def test_multidigraph_ignore2(self): 
241 
# Loop traversed an edge while ignoring its orientation.

242 
G = nx.MultiDiGraph([(0, 1), (1, 2), (1, 2)]) 
243 
x = list(find_cycle(G, [0, 1, 2], orientation='ignore')) 
244 
x_ = [(1, 2, 0, FORWARD), (1, 2, 1, REVERSE)] 
245 
assert_equal(x, x_) 
246  
247 
def test_multidigraph_original(self): 
248 
# Node 2 doesn't need to be searched again from visited from 4.

249 
# The goal here is to cover the case when 2 to be researched from 4,

250 
# when 4 is visited from the first time (so we must make sure that 4

251 
# is not visited from 2, and hence, we respect the edge orientation).

252 
G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 3), (4, 2)]) 
253 
assert_raises(nx.exception.NetworkXNoCycle, 
254 
find_cycle, G, [0, 1, 2, 3, 4], orientation='original') 
255  
256 
def test_dag(self): 
257 
G = nx.DiGraph([(0, 1), (0, 2), (1, 2)]) 
258 
assert_raises(nx.exception.NetworkXNoCycle, 
259 
find_cycle, G, orientation='original')

260 
x = list(find_cycle(G, orientation='ignore')) 
261 
assert_equal(x, [(0, 1, FORWARD), (1, 2, FORWARD), (0, 2, REVERSE)]) 
262  
263 
def test_prev_explored(self): 
264 
# https://github.com/networkx/networkx/issues/2323

265  
266 
G = nx.DiGraph() 
267 
G.add_edges_from([(1, 0), (2, 0), (1, 2), (2, 1)]) 
268 
assert_raises(nx.NetworkXNoCycle, find_cycle, G, source=0)

269 
x = list(nx.find_cycle(G, 1)) 
270 
x_ = [(1, 2), (2, 1)] 
271 
assert_equal(x, x_) 
272  
273 
x = list(nx.find_cycle(G, 2)) 
274 
x_ = [(2, 1), (1, 2)] 
275 
assert_equal(x, x_) 
276  
277 
x = list(nx.find_cycle(G))

278 
x_ = [(1, 2), (2, 1)] 
279 
assert_equal(x, x_) 
280  
281 
def test_no_cycle(self): 
282 
# https://github.com/networkx/networkx/issues/2439

283  
284 
G = nx.DiGraph() 
285 
G.add_edges_from([(1, 2), (2, 0), (3, 1), (3, 2)]) 
286 
assert_raises(nx.NetworkXNoCycle, find_cycle, G, source=0)

287 
assert_raises(nx.NetworkXNoCycle, find_cycle, G) 
288  
289  
290 
def assert_basis_equal(a, b): 
291 
assert_list_equal(sorted(a), sorted(b)) 
292  
293  
294 
class TestMinimumCycles(object): 
295 
def setUp(self): 
296 
T = nx.Graph() 
297 
T.add_cycle([1, 2, 3, 4], weight=1) 
298 
T.add_edge(2, 4, weight=5) 
299 
self.diamond_graph = T

300  
301 
def test_unweighted_diamond(self): 
302 
mcb = minimum_cycle_basis(self.diamond_graph)

303 
assert_basis_equal(mcb, [[1, 2, 4], [2, 3, 4]]) 
304  
305 
def test_weighted_diamond(self): 
306 
mcb = minimum_cycle_basis(self.diamond_graph, weight='weight') 
307 
assert_basis_equal(mcb, [[1, 2, 4], [1, 2, 3, 4]]) 
308  
309 
def test_dimensionality(self): 
310 
# checks MCB=EV+NC

311 
ntrial = 10

312 
for _ in range(ntrial): 
313 
rg = nx.erdos_renyi_graph(10, 0.3) 
314 
nnodes = rg.number_of_nodes() 
315 
nedges = rg.number_of_edges() 
316 
ncomp = nx.number_connected_components(rg) 
317  
318 
dim_mcb = len(minimum_cycle_basis(rg))

319 
assert_equal(dim_mcb, nedges  nnodes + ncomp) 
320  
321 
def test_complete_graph(self): 
322 
cg = nx.complete_graph(5)

323 
mcb = minimum_cycle_basis(cg) 
324 
assert_true(all([len(cycle) == 3 for cycle in mcb])) 
325  
326 
def test_tree_graph(self): 
327 
tg = nx.balanced_tree(3, 3) 
328 
assert_false(minimum_cycle_basis(tg)) 