ioftools / networkxMiCe / networkxmaster / 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 selfloop 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 selfloops."""

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 nonexistent edge raises an

329 
exception.

330 

331 
"""

332 
G = nx.cycle_graph(4)

333 
nx.contracted_edge(G, (0, 2)) 