Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tests / test_minors.py @ 5cef0f13

History | View | Annotate | Download (12.6 KB)

1
# test_minors.py - unit tests for the minors module
2
#
3
# Copyright 2015 Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Unit tests for the :mod:`networkx.algorithms.minors` module."""
10
from nose.tools import assert_equal
11
from nose.tools import assert_true
12
from nose.tools import raises
13

    
14
import networkx as nx
15
from networkx.testing.utils import *
16
from networkx.utils import arbitrary_element
17

    
18

    
19
class TestQuotient(object):
20
    """Unit tests for computing quotient graphs."""
21

    
22
    def test_quotient_graph_complete_multipartite(self):
23
        """Tests that the quotient graph of the complete *n*-partite graph
24
        under the "same neighbors" node relation is the complete graph on *n*
25
        nodes.
26

27
        """
28
        G = nx.complete_multipartite_graph(2, 3, 4)
29
        # Two nodes are equivalent if they are not adjacent but have the same
30
        # neighbor set.
31

    
32
        def same_neighbors(u, v):
33
            return (u not in G[v] and v not in G[u] and G[u] == G[v])
34

    
35
        expected = nx.complete_graph(3)
36
        actual = nx.quotient_graph(G, same_neighbors)
37
        # It won't take too long to run a graph isomorphism algorithm on such
38
        # small graphs.
39
        assert_true(nx.is_isomorphic(expected, actual))
40

    
41
    def test_quotient_graph_complete_bipartite(self):
42
        """Tests that the quotient graph of the complete bipartite graph under
43
        the "same neighbors" node relation is `K_2`.
44

45
        """
46
        G = nx.complete_bipartite_graph(2, 3)
47
        # Two nodes are equivalent if they are not adjacent but have the same
48
        # neighbor set.
49

    
50
        def same_neighbors(u, v):
51
            return (u not in G[v] and v not in G[u] and G[u] == G[v])
52

    
53
        expected = nx.complete_graph(2)
54
        actual = nx.quotient_graph(G, same_neighbors)
55
        # It won't take too long to run a graph isomorphism algorithm on such
56
        # small graphs.
57
        assert_true(nx.is_isomorphic(expected, actual))
58

    
59
    def test_quotient_graph_edge_relation(self):
60
        """Tests for specifying an alternate edge relation for the quotient
61
        graph.
62

63
        """
64
        G = nx.path_graph(5)
65

    
66
        def identity(u, v):
67
            return u == v
68

    
69
        def same_parity(b, c):
70
            return (arbitrary_element(b) % 2 == arbitrary_element(c) % 2)
71

    
72
        actual = nx.quotient_graph(G, identity, same_parity)
73
        expected = nx.Graph()
74
        expected.add_edges_from([(0, 2), (0, 4), (2, 4)])
75
        expected.add_edge(1, 3)
76
        assert_true(nx.is_isomorphic(actual, expected))
77

    
78
    def test_condensation_as_quotient(self):
79
        """This tests that the condensation of a graph can be viewed as the
80
        quotient graph under the "in the same connected component" equivalence
81
        relation.
82

83
        """
84
        # This example graph comes from the file `test_strongly_connected.py`.
85
        G = nx.DiGraph()
86
        G.add_edges_from([(1, 2), (2, 3), (2, 11), (2, 12), (3, 4), (4, 3),
87
                          (4, 5), (5, 6), (6, 5), (6, 7), (7, 8), (7, 9),
88
                          (7, 10), (8, 9), (9, 7), (10, 6), (11, 2), (11, 4),
89
                          (11, 6), (12, 6), (12, 11)])
90
        scc = list(nx.strongly_connected_components(G))
91
        C = nx.condensation(G, scc)
92
        component_of = C.graph['mapping']
93
        # Two nodes are equivalent if they are in the same connected component.
94

    
95
        def same_component(u, v):
96
            return component_of[u] == component_of[v]
97

    
98
        Q = nx.quotient_graph(G, same_component)
99
        assert_true(nx.is_isomorphic(C, Q))
100

    
101
    def test_path(self):
102
        G = nx.path_graph(6)
103
        partition = [{0, 1}, {2, 3}, {4, 5}]
104
        M = nx.quotient_graph(G, partition, relabel=True)
105
        assert_nodes_equal(M, [0, 1, 2])
106
        assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
107
        for n in M:
108
            assert_equal(M.nodes[n]['nedges'], 1)
109
            assert_equal(M.nodes[n]['nnodes'], 2)
110
            assert_equal(M.nodes[n]['density'], 1)
111

    
112
    def test_multigraph_path(self):
113
        G = nx.MultiGraph(nx.path_graph(6))
114
        partition = [{0, 1}, {2, 3}, {4, 5}]
115
        M = nx.quotient_graph(G, partition, relabel=True)
116
        assert_nodes_equal(M, [0, 1, 2])
117
        assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
118
        for n in M:
119
            assert_equal(M.nodes[n]['nedges'], 1)
120
            assert_equal(M.nodes[n]['nnodes'], 2)
121
            assert_equal(M.nodes[n]['density'], 1)
122

    
123
    def test_directed_path(self):
124
        G = nx.DiGraph()
125
        nx.add_path(G, range(6))
126
        partition = [{0, 1}, {2, 3}, {4, 5}]
127
        M = nx.quotient_graph(G, partition, relabel=True)
128
        assert_nodes_equal(M, [0, 1, 2])
129
        assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
130
        for n in M:
131
            assert_equal(M.nodes[n]['nedges'], 1)
132
            assert_equal(M.nodes[n]['nnodes'], 2)
133
            assert_equal(M.nodes[n]['density'], 0.5)
134

    
135
    def test_directed_multigraph_path(self):
136
        G = nx.MultiDiGraph()
137
        nx.add_path(G, range(6))
138
        partition = [{0, 1}, {2, 3}, {4, 5}]
139
        M = nx.quotient_graph(G, partition, relabel=True)
140
        assert_nodes_equal(M, [0, 1, 2])
141
        assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
142
        for n in M:
143
            assert_equal(M.nodes[n]['nedges'], 1)
144
            assert_equal(M.nodes[n]['nnodes'], 2)
145
            assert_equal(M.nodes[n]['density'], 0.5)
146

    
147
    @raises(nx.NetworkXException)
148
    def test_overlapping_blocks(self):
149
        G = nx.path_graph(6)
150
        partition = [{0, 1, 2}, {2, 3}, {4, 5}]
151
        nx.quotient_graph(G, partition)
152

    
153
    def test_weighted_path(self):
154
        G = nx.path_graph(6)
155
        for i in range(5):
156
            G[i][i + 1]['weight'] = i + 1
157
        partition = [{0, 1}, {2, 3}, {4, 5}]
158
        M = nx.quotient_graph(G, partition, relabel=True)
159
        assert_nodes_equal(M, [0, 1, 2])
160
        assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
161
        assert_equal(M[0][1]['weight'], 2)
162
        assert_equal(M[1][2]['weight'], 4)
163
        for n in M:
164
            assert_equal(M.nodes[n]['nedges'], 1)
165
            assert_equal(M.nodes[n]['nnodes'], 2)
166
            assert_equal(M.nodes[n]['density'], 1)
167

    
168
    def test_barbell(self):
169
        G = nx.barbell_graph(3, 0)
170
        partition = [{0, 1, 2}, {3, 4, 5}]
171
        M = nx.quotient_graph(G, partition, relabel=True)
172
        assert_nodes_equal(M, [0, 1])
173
        assert_edges_equal(M.edges(), [(0, 1)])
174
        for n in M:
175
            assert_equal(M.nodes[n]['nedges'], 3)
176
            assert_equal(M.nodes[n]['nnodes'], 3)
177
            assert_equal(M.nodes[n]['density'], 1)
178

    
179
    def test_barbell_plus(self):
180
        G = nx.barbell_graph(3, 0)
181
        # Add an extra edge joining the bells.
182
        G.add_edge(0, 5)
183
        partition = [{0, 1, 2}, {3, 4, 5}]
184
        M = nx.quotient_graph(G, partition, relabel=True)
185
        assert_nodes_equal(M, [0, 1])
186
        assert_edges_equal(M.edges(), [(0, 1)])
187
        assert_equal(M[0][1]['weight'], 2)
188
        for n in M:
189
            assert_equal(M.nodes[n]['nedges'], 3)
190
            assert_equal(M.nodes[n]['nnodes'], 3)
191
            assert_equal(M.nodes[n]['density'], 1)
192

    
193
    def test_blockmodel(self):
194
        G = nx.path_graph(6)
195
        partition = [[0, 1], [2, 3], [4, 5]]
196
        M = nx.quotient_graph(G, partition, relabel=True)
197
        assert_nodes_equal(M.nodes(), [0, 1, 2])
198
        assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
199
        for n in M.nodes():
200
            assert_equal(M.nodes[n]['nedges'], 1)
201
            assert_equal(M.nodes[n]['nnodes'], 2)
202
            assert_equal(M.nodes[n]['density'], 1.0)
203

    
204
    def test_multigraph_blockmodel(self):
205
        G = nx.MultiGraph(nx.path_graph(6))
206
        partition = [[0, 1], [2, 3], [4, 5]]
207
        M = nx.quotient_graph(G, partition,
208
                              create_using=nx.MultiGraph(), relabel=True)
209
        assert_nodes_equal(M.nodes(), [0, 1, 2])
210
        assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
211
        for n in M.nodes():
212
            assert_equal(M.nodes[n]['nedges'], 1)
213
            assert_equal(M.nodes[n]['nnodes'], 2)
214
            assert_equal(M.nodes[n]['density'], 1.0)
215

    
216
    def test_quotient_graph_incomplete_partition(self):
217
        G = nx.path_graph(6)
218
        partition = []
219
        H = nx.quotient_graph(G, partition, relabel=True)
220
        assert_nodes_equal(H.nodes(), [])
221
        assert_edges_equal(H.edges(), [])
222

    
223
        partition = [[0, 1], [2, 3], [5]]
224
        H = nx.quotient_graph(G, partition, relabel=True)
225
        assert_nodes_equal(H.nodes(), [0, 1, 2])
226
        assert_edges_equal(H.edges(), [(0, 1)])
227

    
228

    
229
class TestContraction(object):
230
    """Unit tests for node and edge contraction functions."""
231

    
232
    def test_undirected_node_contraction(self):
233
        """Tests for node contraction in an undirected graph."""
234
        G = nx.cycle_graph(4)
235
        actual = nx.contracted_nodes(G, 0, 1)
236
        expected = nx.complete_graph(3)
237
        expected.add_edge(0, 0)
238
        assert_true(nx.is_isomorphic(actual, expected))
239

    
240
    def test_directed_node_contraction(self):
241
        """Tests for node contraction in a directed graph."""
242
        G = nx.DiGraph(nx.cycle_graph(4))
243
        actual = nx.contracted_nodes(G, 0, 1)
244
        expected = nx.DiGraph(nx.complete_graph(3))
245
        expected.add_edge(0, 0)
246
        expected.add_edge(0, 0)
247
        assert_true(nx.is_isomorphic(actual, expected))
248

    
249
    def test_create_multigraph(self):
250
        """Tests that using a MultiGraph creates multiple edges."""
251
        G = nx.path_graph(3, create_using=nx.MultiGraph())
252
        G.add_edge(0, 1)
253
        G.add_edge(0, 0)
254
        G.add_edge(0, 2)
255
        actual = nx.contracted_nodes(G, 0, 2)
256
        expected = nx.MultiGraph()
257
        expected.add_edge(0, 1)
258
        expected.add_edge(0, 1)
259
        expected.add_edge(0, 1)
260
        expected.add_edge(0, 0)
261
        expected.add_edge(0, 0)
262
        assert_edges_equal(actual.edges, expected.edges)
263

    
264
    def test_multigraph_keys(self):
265
        """Tests that multiedge keys are reset in new graph."""
266
        G = nx.path_graph(3, create_using=nx.MultiGraph())
267
        G.add_edge(0, 1, 5)
268
        G.add_edge(0, 0, 0)
269
        G.add_edge(0, 2, 5)
270
        actual = nx.contracted_nodes(G, 0, 2)
271
        expected = nx.MultiGraph()
272
        expected.add_edge(0, 1, 0)
273
        expected.add_edge(0, 1, 5)
274
        expected.add_edge(0, 1, 2)  # keyed as 2 b/c 2 edges already in G
275
        expected.add_edge(0, 0, 0)
276
        expected.add_edge(0, 0, 1)  # this comes from (0, 2, 5)
277
        assert_edges_equal(actual.edges, expected.edges)
278

    
279
    def test_node_attributes(self):
280
        """Tests that node contraction preserves node attributes."""
281
        G = nx.cycle_graph(4)
282
        # Add some data to the two nodes being contracted.
283
        G.nodes[0]['foo'] = 'bar'
284
        G.nodes[1]['baz'] = 'xyzzy'
285
        actual = nx.contracted_nodes(G, 0, 1)
286
        # We expect that contracting the nodes 0 and 1 in C_4 yields K_3, but
287
        # with nodes labeled 0, 2, and 3, and with a self-loop on 0.
288
        expected = nx.complete_graph(3)
289
        expected = nx.relabel_nodes(expected, {1: 2, 2: 3})
290
        expected.add_edge(0, 0)
291
        cdict = {1: {'baz': 'xyzzy'}}
292
        expected.nodes[0].update(dict(foo='bar', contraction=cdict))
293
        assert_true(nx.is_isomorphic(actual, expected))
294
        assert_equal(actual.nodes, expected.nodes)
295

    
296
    def test_without_self_loops(self):
297
        """Tests for node contraction without preserving self-loops."""
298
        G = nx.cycle_graph(4)
299
        actual = nx.contracted_nodes(G, 0, 1, self_loops=False)
300
        expected = nx.complete_graph(3)
301
        assert_true(nx.is_isomorphic(actual, expected))
302

    
303
    def test_contract_selfloop_graph(self):
304
        """Tests for node contraction when nodes have selfloops."""
305
        G = nx.cycle_graph(4)
306
        G.add_edge(0, 0)
307
        actual = nx.contracted_nodes(G, 0, 1)
308
        expected = nx.complete_graph([0, 2, 3])
309
        expected.add_edge(0, 0)
310
        expected.add_edge(0, 0)
311
        assert_edges_equal(actual.edges, expected.edges)
312
        actual = nx.contracted_nodes(G, 1, 0)
313
        expected = nx.complete_graph([1, 2, 3])
314
        expected.add_edge(1, 1)
315
        expected.add_edge(1, 1)
316
        assert_edges_equal(actual.edges, expected.edges)
317

    
318
    def test_undirected_edge_contraction(self):
319
        """Tests for edge contraction in an undirected graph."""
320
        G = nx.cycle_graph(4)
321
        actual = nx.contracted_edge(G, (0, 1))
322
        expected = nx.complete_graph(3)
323
        expected.add_edge(0, 0)
324
        assert_true(nx.is_isomorphic(actual, expected))
325

    
326
    @raises(ValueError)
327
    def test_nonexistent_edge(self):
328
        """Tests that attempting to contract a non-existent edge raises an
329
        exception.
330

331
        """
332
        G = nx.cycle_graph(4)
333
        nx.contracted_edge(G, (0, 2))