Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (13 KB)

1
import networkx as nx
2
from nose.tools import assert_true, assert_equal, raises
3
from networkx.testing import assert_edges_equal
4

    
5

    
6
@raises(nx.NetworkXError)
7
def test_tensor_product_raises():
8
    P = nx.tensor_product(nx.DiGraph(), nx.Graph())
9

    
10

    
11
def test_tensor_product_null():
12
    null = nx.null_graph()
13
    empty10 = nx.empty_graph(10)
14
    K3 = nx.complete_graph(3)
15
    K10 = nx.complete_graph(10)
16
    P3 = nx.path_graph(3)
17
    P10 = nx.path_graph(10)
18
    # null graph
19
    G = nx.tensor_product(null, null)
20
    assert_true(nx.is_isomorphic(G, null))
21
    # null_graph X anything = null_graph and v.v.
22
    G = nx.tensor_product(null, empty10)
23
    assert_true(nx.is_isomorphic(G, null))
24
    G = nx.tensor_product(null, K3)
25
    assert_true(nx.is_isomorphic(G, null))
26
    G = nx.tensor_product(null, K10)
27
    assert_true(nx.is_isomorphic(G, null))
28
    G = nx.tensor_product(null, P3)
29
    assert_true(nx.is_isomorphic(G, null))
30
    G = nx.tensor_product(null, P10)
31
    assert_true(nx.is_isomorphic(G, null))
32
    G = nx.tensor_product(empty10, null)
33
    assert_true(nx.is_isomorphic(G, null))
34
    G = nx.tensor_product(K3, null)
35
    assert_true(nx.is_isomorphic(G, null))
36
    G = nx.tensor_product(K10, null)
37
    assert_true(nx.is_isomorphic(G, null))
38
    G = nx.tensor_product(P3, null)
39
    assert_true(nx.is_isomorphic(G, null))
40
    G = nx.tensor_product(P10, null)
41
    assert_true(nx.is_isomorphic(G, null))
42

    
43

    
44
def test_tensor_product_size():
45
    P5 = nx.path_graph(5)
46
    K3 = nx.complete_graph(3)
47
    K5 = nx.complete_graph(5)
48

    
49
    G = nx.tensor_product(P5, K3)
50
    assert_equal(nx.number_of_nodes(G), 5 * 3)
51
    G = nx.tensor_product(K3, K5)
52
    assert_equal(nx.number_of_nodes(G), 3 * 5)
53

    
54

    
55
def test_tensor_product_combinations():
56
    # basic smoke test, more realistic tests would be useful
57
    P5 = nx.path_graph(5)
58
    K3 = nx.complete_graph(3)
59
    G = nx.tensor_product(P5, K3)
60
    assert_equal(nx.number_of_nodes(G), 5 * 3)
61
    G = nx.tensor_product(P5, nx.MultiGraph(K3))
62
    assert_equal(nx.number_of_nodes(G), 5 * 3)
63
    G = nx.tensor_product(nx.MultiGraph(P5), K3)
64
    assert_equal(nx.number_of_nodes(G), 5 * 3)
65
    G = nx.tensor_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
66
    assert_equal(nx.number_of_nodes(G), 5 * 3)
67

    
68
    G = nx.tensor_product(nx.DiGraph(P5), nx.DiGraph(K3))
69
    assert_equal(nx.number_of_nodes(G), 5 * 3)
70

    
71

    
72
def test_tensor_product_classic_result():
73
    K2 = nx.complete_graph(2)
74
    G = nx.petersen_graph()
75
    G = nx.tensor_product(G, K2)
76
    assert_true(nx.is_isomorphic(G, nx.desargues_graph()))
77

    
78
    G = nx.cycle_graph(5)
79
    G = nx.tensor_product(G, K2)
80
    assert_true(nx.is_isomorphic(G, nx.cycle_graph(10)))
81

    
82
    G = nx.tetrahedral_graph()
83
    G = nx.tensor_product(G, K2)
84
    assert_true(nx.is_isomorphic(G, nx.cubical_graph()))
85

    
86

    
87
def test_tensor_product_random():
88
    G = nx.erdos_renyi_graph(10, 2 / 10.)
89
    H = nx.erdos_renyi_graph(10, 2 / 10.)
90
    GH = nx.tensor_product(G, H)
91

    
92
    for (u_G, u_H) in GH.nodes():
93
        for (v_G, v_H) in GH.nodes():
94
            if H.has_edge(u_H, v_H) and G.has_edge(u_G, v_G):
95
                assert_true(GH.has_edge((u_G, u_H), (v_G, v_H)))
96
            else:
97
                assert_true(not GH.has_edge((u_G, u_H), (v_G, v_H)))
98

    
99

    
100
def test_cartesian_product_multigraph():
101
    G = nx.MultiGraph()
102
    G.add_edge(1, 2, key=0)
103
    G.add_edge(1, 2, key=1)
104
    H = nx.MultiGraph()
105
    H.add_edge(3, 4, key=0)
106
    H.add_edge(3, 4, key=1)
107
    GH = nx.cartesian_product(G, H)
108
    assert_equal(set(GH), {(1, 3), (2, 3), (2, 4), (1, 4)})
109
    assert_equal({(frozenset([u, v]), k) for u, v, k in GH.edges(keys=True)},
110
                 {(frozenset([u, v]), k) for u, v, k in
111
                  [((1, 3), (2, 3), 0), ((1, 3), (2, 3), 1),
112
                   ((1, 3), (1, 4), 0), ((1, 3), (1, 4), 1),
113
                   ((2, 3), (2, 4), 0), ((2, 3), (2, 4), 1),
114
                   ((2, 4), (1, 4), 0), ((2, 4), (1, 4), 1)]})
115

    
116

    
117
@raises(nx.NetworkXError)
118
def test_cartesian_product_raises():
119
    P = nx.cartesian_product(nx.DiGraph(), nx.Graph())
120

    
121

    
122
def test_cartesian_product_null():
123
    null = nx.null_graph()
124
    empty10 = nx.empty_graph(10)
125
    K3 = nx.complete_graph(3)
126
    K10 = nx.complete_graph(10)
127
    P3 = nx.path_graph(3)
128
    P10 = nx.path_graph(10)
129
    # null graph
130
    G = nx.cartesian_product(null, null)
131
    assert_true(nx.is_isomorphic(G, null))
132
    # null_graph X anything = null_graph and v.v.
133
    G = nx.cartesian_product(null, empty10)
134
    assert_true(nx.is_isomorphic(G, null))
135
    G = nx.cartesian_product(null, K3)
136
    assert_true(nx.is_isomorphic(G, null))
137
    G = nx.cartesian_product(null, K10)
138
    assert_true(nx.is_isomorphic(G, null))
139
    G = nx.cartesian_product(null, P3)
140
    assert_true(nx.is_isomorphic(G, null))
141
    G = nx.cartesian_product(null, P10)
142
    assert_true(nx.is_isomorphic(G, null))
143
    G = nx.cartesian_product(empty10, null)
144
    assert_true(nx.is_isomorphic(G, null))
145
    G = nx.cartesian_product(K3, null)
146
    assert_true(nx.is_isomorphic(G, null))
147
    G = nx.cartesian_product(K10, null)
148
    assert_true(nx.is_isomorphic(G, null))
149
    G = nx.cartesian_product(P3, null)
150
    assert_true(nx.is_isomorphic(G, null))
151
    G = nx.cartesian_product(P10, null)
152
    assert_true(nx.is_isomorphic(G, null))
153

    
154

    
155
def test_cartesian_product_size():
156
    # order(GXH)=order(G)*order(H)
157
    K5 = nx.complete_graph(5)
158
    P5 = nx.path_graph(5)
159
    K3 = nx.complete_graph(3)
160
    G = nx.cartesian_product(P5, K3)
161
    assert_equal(nx.number_of_nodes(G), 5 * 3)
162
    assert_equal(nx.number_of_edges(G),
163
                 nx.number_of_edges(P5) * nx.number_of_nodes(K3) +
164
                 nx.number_of_edges(K3) * nx.number_of_nodes(P5))
165
    G = nx.cartesian_product(K3, K5)
166
    assert_equal(nx.number_of_nodes(G), 3 * 5)
167
    assert_equal(nx.number_of_edges(G),
168
                 nx.number_of_edges(K5) * nx.number_of_nodes(K3) +
169
                 nx.number_of_edges(K3) * nx.number_of_nodes(K5))
170

    
171

    
172
def test_cartesian_product_classic():
173
    # test some classic product graphs
174
    P2 = nx.path_graph(2)
175
    P3 = nx.path_graph(3)
176
    # cube = 2-path X 2-path
177
    G = nx.cartesian_product(P2, P2)
178
    G = nx.cartesian_product(P2, G)
179
    assert_true(nx.is_isomorphic(G, nx.cubical_graph()))
180

    
181
    # 3x3 grid
182
    G = nx.cartesian_product(P3, P3)
183
    assert_true(nx.is_isomorphic(G, nx.grid_2d_graph(3, 3)))
184

    
185

    
186
def test_cartesian_product_random():
187
    G = nx.erdos_renyi_graph(10, 2 / 10.)
188
    H = nx.erdos_renyi_graph(10, 2 / 10.)
189
    GH = nx.cartesian_product(G, H)
190

    
191
    for (u_G, u_H) in GH.nodes():
192
        for (v_G, v_H) in GH.nodes():
193
            if (u_G == v_G and H.has_edge(u_H, v_H)) or \
194
               (u_H == v_H and G.has_edge(u_G, v_G)):
195
                assert_true(GH.has_edge((u_G, u_H), (v_G, v_H)))
196
            else:
197
                assert_true(not GH.has_edge((u_G, u_H), (v_G, v_H)))
198

    
199

    
200
@raises(nx.NetworkXError)
201
def test_lexicographic_product_raises():
202
    P = nx.lexicographic_product(nx.DiGraph(), nx.Graph())
203

    
204

    
205
def test_lexicographic_product_null():
206
    null = nx.null_graph()
207
    empty10 = nx.empty_graph(10)
208
    K3 = nx.complete_graph(3)
209
    K10 = nx.complete_graph(10)
210
    P3 = nx.path_graph(3)
211
    P10 = nx.path_graph(10)
212
    # null graph
213
    G = nx.lexicographic_product(null, null)
214
    assert_true(nx.is_isomorphic(G, null))
215
    # null_graph X anything = null_graph and v.v.
216
    G = nx.lexicographic_product(null, empty10)
217
    assert_true(nx.is_isomorphic(G, null))
218
    G = nx.lexicographic_product(null, K3)
219
    assert_true(nx.is_isomorphic(G, null))
220
    G = nx.lexicographic_product(null, K10)
221
    assert_true(nx.is_isomorphic(G, null))
222
    G = nx.lexicographic_product(null, P3)
223
    assert_true(nx.is_isomorphic(G, null))
224
    G = nx.lexicographic_product(null, P10)
225
    assert_true(nx.is_isomorphic(G, null))
226
    G = nx.lexicographic_product(empty10, null)
227
    assert_true(nx.is_isomorphic(G, null))
228
    G = nx.lexicographic_product(K3, null)
229
    assert_true(nx.is_isomorphic(G, null))
230
    G = nx.lexicographic_product(K10, null)
231
    assert_true(nx.is_isomorphic(G, null))
232
    G = nx.lexicographic_product(P3, null)
233
    assert_true(nx.is_isomorphic(G, null))
234
    G = nx.lexicographic_product(P10, null)
235
    assert_true(nx.is_isomorphic(G, null))
236

    
237

    
238
def test_lexicographic_product_size():
239
    K5 = nx.complete_graph(5)
240
    P5 = nx.path_graph(5)
241
    K3 = nx.complete_graph(3)
242
    G = nx.lexicographic_product(P5, K3)
243
    assert_equal(nx.number_of_nodes(G), 5 * 3)
244
    G = nx.lexicographic_product(K3, K5)
245
    assert_equal(nx.number_of_nodes(G), 3 * 5)
246

    
247

    
248
def test_lexicographic_product_combinations():
249
    P5 = nx.path_graph(5)
250
    K3 = nx.complete_graph(3)
251
    G = nx.lexicographic_product(P5, K3)
252
    assert_equal(nx.number_of_nodes(G), 5 * 3)
253
    G = nx.lexicographic_product(nx.MultiGraph(P5), K3)
254
    assert_equal(nx.number_of_nodes(G), 5 * 3)
255
    G = nx.lexicographic_product(P5, nx.MultiGraph(K3))
256
    assert_equal(nx.number_of_nodes(G), 5 * 3)
257
    G = nx.lexicographic_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
258
    assert_equal(nx.number_of_nodes(G), 5 * 3)
259

    
260
    # No classic easily found classic results for lexicographic product
261

    
262

    
263
def test_lexicographic_product_random():
264
    G = nx.erdos_renyi_graph(10, 2 / 10.)
265
    H = nx.erdos_renyi_graph(10, 2 / 10.)
266
    GH = nx.lexicographic_product(G, H)
267

    
268
    for (u_G, u_H) in GH.nodes():
269
        for (v_G, v_H) in GH.nodes():
270
            if G.has_edge(u_G, v_G) or (u_G == v_G and H.has_edge(u_H, v_H)):
271
                assert_true(GH.has_edge((u_G, u_H), (v_G, v_H)))
272
            else:
273
                assert_true(not GH.has_edge((u_G, u_H), (v_G, v_H)))
274

    
275

    
276
@raises(nx.NetworkXError)
277
def test_strong_product_raises():
278
    P = nx.strong_product(nx.DiGraph(), nx.Graph())
279

    
280

    
281
def test_strong_product_null():
282
    null = nx.null_graph()
283
    empty10 = nx.empty_graph(10)
284
    K3 = nx.complete_graph(3)
285
    K10 = nx.complete_graph(10)
286
    P3 = nx.path_graph(3)
287
    P10 = nx.path_graph(10)
288
    # null graph
289
    G = nx.strong_product(null, null)
290
    assert_true(nx.is_isomorphic(G, null))
291
    # null_graph X anything = null_graph and v.v.
292
    G = nx.strong_product(null, empty10)
293
    assert_true(nx.is_isomorphic(G, null))
294
    G = nx.strong_product(null, K3)
295
    assert_true(nx.is_isomorphic(G, null))
296
    G = nx.strong_product(null, K10)
297
    assert_true(nx.is_isomorphic(G, null))
298
    G = nx.strong_product(null, P3)
299
    assert_true(nx.is_isomorphic(G, null))
300
    G = nx.strong_product(null, P10)
301
    assert_true(nx.is_isomorphic(G, null))
302
    G = nx.strong_product(empty10, null)
303
    assert_true(nx.is_isomorphic(G, null))
304
    G = nx.strong_product(K3, null)
305
    assert_true(nx.is_isomorphic(G, null))
306
    G = nx.strong_product(K10, null)
307
    assert_true(nx.is_isomorphic(G, null))
308
    G = nx.strong_product(P3, null)
309
    assert_true(nx.is_isomorphic(G, null))
310
    G = nx.strong_product(P10, null)
311
    assert_true(nx.is_isomorphic(G, null))
312

    
313

    
314
def test_strong_product_size():
315
    K5 = nx.complete_graph(5)
316
    P5 = nx.path_graph(5)
317
    K3 = nx.complete_graph(3)
318
    G = nx.strong_product(P5, K3)
319
    assert_equal(nx.number_of_nodes(G), 5 * 3)
320
    G = nx.strong_product(K3, K5)
321
    assert_equal(nx.number_of_nodes(G), 3 * 5)
322

    
323

    
324
def test_strong_product_combinations():
325
    P5 = nx.path_graph(5)
326
    K3 = nx.complete_graph(3)
327
    G = nx.strong_product(P5, K3)
328
    assert_equal(nx.number_of_nodes(G), 5 * 3)
329
    G = nx.strong_product(nx.MultiGraph(P5), K3)
330
    assert_equal(nx.number_of_nodes(G), 5 * 3)
331
    G = nx.strong_product(P5, nx.MultiGraph(K3))
332
    assert_equal(nx.number_of_nodes(G), 5 * 3)
333
    G = nx.strong_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
334
    assert_equal(nx.number_of_nodes(G), 5 * 3)
335

    
336
    # No classic easily found classic results for strong product
337

    
338

    
339
def test_strong_product_random():
340
    G = nx.erdos_renyi_graph(10, 2 / 10.)
341
    H = nx.erdos_renyi_graph(10, 2 / 10.)
342
    GH = nx.strong_product(G, H)
343

    
344
    for (u_G, u_H) in GH.nodes():
345
        for (v_G, v_H) in GH.nodes():
346
            if (u_G == v_G and H.has_edge(u_H, v_H)) or \
347
               (u_H == v_H and G.has_edge(u_G, v_G)) or \
348
               (G.has_edge(u_G, v_G) and H.has_edge(u_H, v_H)):
349
                assert_true(GH.has_edge((u_G, u_H), (v_G, v_H)))
350
            else:
351
                assert_true(not GH.has_edge((u_G, u_H), (v_G, v_H)))
352

    
353

    
354
@raises(nx.NetworkXNotImplemented)
355
def test_graph_power_raises():
356
    nx.power(nx.MultiDiGraph(), 2)
357

    
358

    
359
def test_graph_power():
360
    # wikipedia example for graph power
361
    G = nx.cycle_graph(7)
362
    G.add_edge(6, 7)
363
    G.add_edge(7, 8)
364
    G.add_edge(8, 9)
365
    G.add_edge(9, 2)
366
    H = nx.power(G, 2)
367

    
368
    assert_edges_equal(list(H.edges()),
369
                       [(0, 1), (0, 2), (0, 5), (0, 6), (0, 7), (1, 9),
370
                        (1, 2), (1, 3), (1, 6), (2, 3), (2, 4), (2, 8),
371
                        (2, 9), (3, 4), (3, 5), (3, 9), (4, 5), (4, 6),
372
                        (5, 6), (5, 7), (6, 7), (6, 8), (7, 8), (7, 9),
373
                        (8, 9)])
374

    
375

    
376
@raises(ValueError)
377
def test_graph_power_negative():
378
    nx.power(nx.Graph(), -1)
379

    
380

    
381
@raises(nx.NetworkXError)
382
def test_rooted_product_raises():
383
    nx.rooted_product(nx.Graph(), nx.path_graph(2), 10)
384

    
385

    
386
def test_rooted_product():
387
    G = nx.cycle_graph(5)
388
    H = nx.Graph()
389
    H.add_edges_from([('a', 'b'), ('b', 'c'), ('b', 'd')])
390
    R = nx.rooted_product(G, H, 'a')
391
    assert_equal(len(R), len(G) * len(H))
392
    assert_equal(R.size(), G.size() + len(G) * H.size())