Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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|=|E|-|V|+|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))