Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.7 KB)

1
from nose.tools import *
2
import networkx as nx
3
from networkx import *
4
from networkx.testing import *
5

    
6

    
7
def test_union_attributes():
8
    g = nx.Graph()
9
    g.add_node(0, x=4)
10
    g.add_node(1, x=5)
11
    g.add_edge(0, 1, size=5)
12
    g.graph['name'] = 'g'
13

    
14
    h = g.copy()
15
    h.graph['name'] = 'h'
16
    h.graph['attr'] = 'attr'
17
    h.nodes[0]['x'] = 7
18

    
19
    gh = nx.union(g, h, rename=('g', 'h'))
20
    assert_equal(set(gh.nodes()), set(['h0', 'h1', 'g0', 'g1']))
21
    for n in gh:
22
        graph, node = n
23
        assert_equal(gh.nodes[n], eval(graph).nodes[int(node)])
24

    
25
    assert_equal(gh.graph['attr'], 'attr')
26
    assert_equal(gh.graph['name'], 'h')  # h graph attributes take precendent
27

    
28

    
29
def test_intersection():
30
    G = nx.Graph()
31
    H = nx.Graph()
32
    G.add_nodes_from([1, 2, 3, 4])
33
    G.add_edge(1, 2)
34
    G.add_edge(2, 3)
35
    H.add_nodes_from([1, 2, 3, 4])
36
    H.add_edge(2, 3)
37
    H.add_edge(3, 4)
38
    I = nx.intersection(G, H)
39
    assert_equal(set(I.nodes()), set([1, 2, 3, 4]))
40
    assert_equal(sorted(I.edges()), [(2, 3)])
41

    
42

    
43
def test_intersection_attributes():
44
    g = nx.Graph()
45
    g.add_node(0, x=4)
46
    g.add_node(1, x=5)
47
    g.add_edge(0, 1, size=5)
48
    g.graph['name'] = 'g'
49

    
50
    h = g.copy()
51
    h.graph['name'] = 'h'
52
    h.graph['attr'] = 'attr'
53
    h.nodes[0]['x'] = 7
54

    
55
    gh = nx.intersection(g, h)
56
    assert_equal(set(gh.nodes()), set(g.nodes()))
57
    assert_equal(set(gh.nodes()), set(h.nodes()))
58
    assert_equal(sorted(gh.edges()), sorted(g.edges()))
59

    
60
    h.remove_node(0)
61
    assert_raises(nx.NetworkXError, nx.intersection, g, h)
62

    
63

    
64
def test_intersection_multigraph_attributes():
65
    g = nx.MultiGraph()
66
    g.add_edge(0, 1, key=0)
67
    g.add_edge(0, 1, key=1)
68
    g.add_edge(0, 1, key=2)
69
    h = nx.MultiGraph()
70
    h.add_edge(0, 1, key=0)
71
    h.add_edge(0, 1, key=3)
72
    gh = nx.intersection(g, h)
73
    assert_equal(set(gh.nodes()), set(g.nodes()))
74
    assert_equal(set(gh.nodes()), set(h.nodes()))
75
    assert_equal(sorted(gh.edges()), [(0, 1)])
76
    assert_equal(sorted(gh.edges(keys=True)), [(0, 1, 0)])
77

    
78

    
79
def test_difference():
80
    G = nx.Graph()
81
    H = nx.Graph()
82
    G.add_nodes_from([1, 2, 3, 4])
83
    G.add_edge(1, 2)
84
    G.add_edge(2, 3)
85
    H.add_nodes_from([1, 2, 3, 4])
86
    H.add_edge(2, 3)
87
    H.add_edge(3, 4)
88
    D = nx.difference(G, H)
89
    assert_equal(set(D.nodes()), set([1, 2, 3, 4]))
90
    assert_equal(sorted(D.edges()), [(1, 2)])
91
    D = nx.difference(H, G)
92
    assert_equal(set(D.nodes()), set([1, 2, 3, 4]))
93
    assert_equal(sorted(D.edges()), [(3, 4)])
94
    D = nx.symmetric_difference(G, H)
95
    assert_equal(set(D.nodes()), set([1, 2, 3, 4]))
96
    assert_equal(sorted(D.edges()), [(1, 2), (3, 4)])
97

    
98

    
99
def test_difference2():
100
    G = nx.Graph()
101
    H = nx.Graph()
102
    G.add_nodes_from([1, 2, 3, 4])
103
    H.add_nodes_from([1, 2, 3, 4])
104
    G.add_edge(1, 2)
105
    H.add_edge(1, 2)
106
    G.add_edge(2, 3)
107
    D = nx.difference(G, H)
108
    assert_equal(set(D.nodes()), set([1, 2, 3, 4]))
109
    assert_equal(sorted(D.edges()), [(2, 3)])
110
    D = nx.difference(H, G)
111
    assert_equal(set(D.nodes()), set([1, 2, 3, 4]))
112
    assert_equal(sorted(D.edges()), [])
113
    H.add_edge(3, 4)
114
    D = nx.difference(H, G)
115
    assert_equal(set(D.nodes()), set([1, 2, 3, 4]))
116
    assert_equal(sorted(D.edges()), [(3, 4)])
117

    
118

    
119
def test_difference_attributes():
120
    g = nx.Graph()
121
    g.add_node(0, x=4)
122
    g.add_node(1, x=5)
123
    g.add_edge(0, 1, size=5)
124
    g.graph['name'] = 'g'
125

    
126
    h = g.copy()
127
    h.graph['name'] = 'h'
128
    h.graph['attr'] = 'attr'
129
    h.nodes[0]['x'] = 7
130

    
131
    gh = nx.difference(g, h)
132
    assert_equal(set(gh.nodes()), set(g.nodes()))
133
    assert_equal(set(gh.nodes()), set(h.nodes()))
134
    assert_equal(sorted(gh.edges()), [])
135

    
136
    h.remove_node(0)
137
    assert_raises(nx.NetworkXError, nx.intersection, g, h)
138

    
139

    
140
def test_difference_multigraph_attributes():
141
    g = nx.MultiGraph()
142
    g.add_edge(0, 1, key=0)
143
    g.add_edge(0, 1, key=1)
144
    g.add_edge(0, 1, key=2)
145
    h = nx.MultiGraph()
146
    h.add_edge(0, 1, key=0)
147
    h.add_edge(0, 1, key=3)
148
    gh = nx.difference(g, h)
149
    assert_equal(set(gh.nodes()), set(g.nodes()))
150
    assert_equal(set(gh.nodes()), set(h.nodes()))
151
    assert_equal(sorted(gh.edges()), [(0, 1), (0, 1)])
152
    assert_equal(sorted(gh.edges(keys=True)), [(0, 1, 1), (0, 1, 2)])
153

    
154

    
155
@raises(nx.NetworkXError)
156
def test_difference_raise():
157
    G = nx.path_graph(4)
158
    H = nx.path_graph(3)
159
    GH = nx.difference(G, H)
160

    
161

    
162
def test_symmetric_difference_multigraph():
163
    g = nx.MultiGraph()
164
    g.add_edge(0, 1, key=0)
165
    g.add_edge(0, 1, key=1)
166
    g.add_edge(0, 1, key=2)
167
    h = nx.MultiGraph()
168
    h.add_edge(0, 1, key=0)
169
    h.add_edge(0, 1, key=3)
170
    gh = nx.symmetric_difference(g, h)
171
    assert_equal(set(gh.nodes()), set(g.nodes()))
172
    assert_equal(set(gh.nodes()), set(h.nodes()))
173
    assert_equal(sorted(gh.edges()), 3 * [(0, 1)])
174
    assert_equal(sorted(sorted(e) for e in gh.edges(keys=True)),
175
                 [[0, 1, 1], [0, 1, 2], [0, 1, 3]])
176

    
177

    
178
@raises(nx.NetworkXError)
179
def test_symmetric_difference_raise():
180
    G = nx.path_graph(4)
181
    H = nx.path_graph(3)
182
    GH = nx.symmetric_difference(G, H)
183

    
184

    
185
def test_union_and_compose():
186
    K3 = complete_graph(3)
187
    P3 = path_graph(3)
188

    
189
    G1 = nx.DiGraph()
190
    G1.add_edge('A', 'B')
191
    G1.add_edge('A', 'C')
192
    G1.add_edge('A', 'D')
193
    G2 = nx.DiGraph()
194
    G2.add_edge('1', '2')
195
    G2.add_edge('1', '3')
196
    G2.add_edge('1', '4')
197

    
198
    G = union(G1, G2)
199
    H = compose(G1, G2)
200
    assert_edges_equal(G.edges(), H.edges())
201
    assert_false(G.has_edge('A', 1))
202
    assert_raises(nx.NetworkXError, nx.union, K3, P3)
203
    H1 = union(H, G1, rename=('H', 'G1'))
204
    assert_equal(sorted(H1.nodes()),
205
                 ['G1A', 'G1B', 'G1C', 'G1D',
206
                  'H1', 'H2', 'H3', 'H4', 'HA', 'HB', 'HC', 'HD'])
207

    
208
    H2 = union(H, G2, rename=("H", ""))
209
    assert_equal(sorted(H2.nodes()),
210
                 ['1', '2', '3', '4',
211
                  'H1', 'H2', 'H3', 'H4', 'HA', 'HB', 'HC', 'HD'])
212

    
213
    assert_false(H1.has_edge('NB', 'NA'))
214

    
215
    G = compose(G, G)
216
    assert_edges_equal(G.edges(), H.edges())
217

    
218
    G2 = union(G2, G2, rename=('', 'copy'))
219
    assert_equal(sorted(G2.nodes()),
220
                 ['1', '2', '3', '4', 'copy1', 'copy2', 'copy3', 'copy4'])
221

    
222
    assert_equal(sorted(G2.neighbors('copy4')), [])
223
    assert_equal(sorted(G2.neighbors('copy1')), ['copy2', 'copy3', 'copy4'])
224
    assert_equal(len(G), 8)
225
    assert_equal(number_of_edges(G), 6)
226

    
227
    E = disjoint_union(G, G)
228
    assert_equal(len(E), 16)
229
    assert_equal(number_of_edges(E), 12)
230

    
231
    E = disjoint_union(G1, G2)
232
    assert_equal(sorted(E.nodes()), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
233

    
234
    G = nx.Graph()
235
    H = nx.Graph()
236
    G.add_nodes_from([(1, {'a1': 1})])
237
    H.add_nodes_from([(1, {'b1': 1})])
238
    R = compose(G, H)
239
    assert_equal(R.nodes, {1: {'a1': 1, 'b1': 1}})
240

    
241

    
242
def test_union_multigraph():
243
    G = nx.MultiGraph()
244
    G.add_edge(1, 2, key=0)
245
    G.add_edge(1, 2, key=1)
246
    H = nx.MultiGraph()
247
    H.add_edge(3, 4, key=0)
248
    H.add_edge(3, 4, key=1)
249
    GH = nx.union(G, H)
250
    assert_equal(set(GH), set(G) | set(H))
251
    assert_equal(set(GH.edges(keys=True)),
252
                 set(G.edges(keys=True)) | set(H.edges(keys=True)))
253

    
254

    
255
def test_disjoint_union_multigraph():
256
    G = nx.MultiGraph()
257
    G.add_edge(0, 1, key=0)
258
    G.add_edge(0, 1, key=1)
259
    H = nx.MultiGraph()
260
    H.add_edge(2, 3, key=0)
261
    H.add_edge(2, 3, key=1)
262
    GH = nx.disjoint_union(G, H)
263
    assert_equal(set(GH), set(G) | set(H))
264
    assert_equal(set(GH.edges(keys=True)),
265
                 set(G.edges(keys=True)) | set(H.edges(keys=True)))
266

    
267

    
268
def test_compose_multigraph():
269
    G = nx.MultiGraph()
270
    G.add_edge(1, 2, key=0)
271
    G.add_edge(1, 2, key=1)
272
    H = nx.MultiGraph()
273
    H.add_edge(3, 4, key=0)
274
    H.add_edge(3, 4, key=1)
275
    GH = nx.compose(G, H)
276
    assert_equal(set(GH), set(G) | set(H))
277
    assert_equal(set(GH.edges(keys=True)),
278
                 set(G.edges(keys=True)) | set(H.edges(keys=True)))
279
    H.add_edge(1, 2, key=2)
280
    GH = nx.compose(G, H)
281
    assert_equal(set(GH), set(G) | set(H))
282
    assert_equal(set(GH.edges(keys=True)),
283
                 set(G.edges(keys=True)) | set(H.edges(keys=True)))
284

    
285

    
286
def test_full_join_graph():
287
    # Simple Graphs
288
    G = nx.Graph()
289
    G.add_node(0)
290
    G.add_edge(1, 2)
291
    H = nx.Graph()
292
    H.add_edge(3, 4)
293

    
294
    U = nx.full_join(G, H)
295
    assert_equal(set(U), set(G) | set(H))
296
    assert_equal(len(U), len(G) + len(H))
297
    assert_equal(len(U.edges()),
298
                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
299
                 )
300

    
301
    # Rename
302
    U = nx.full_join(G, H, rename=('g', 'h'))
303
    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
304
    assert_equal(len(U), len(G) + len(H))
305
    assert_equal(len(U.edges()),
306
                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
307
                 )
308

    
309
    # Rename graphs with string-like nodes
310
    G = nx.Graph()
311
    G.add_node("a")
312
    G.add_edge("b", "c")
313
    H = nx.Graph()
314
    H.add_edge("d", "e")
315

    
316
    U = nx.full_join(G, H, rename=('g', 'h'))
317
    assert_equal(set(U), set(['ga', 'gb', 'gc', 'hd', 'he']))
318
    assert_equal(len(U), len(G) + len(H))
319
    assert_equal(len(U.edges()),
320
                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
321
                 )
322

    
323
    # DiGraphs
324
    G = nx.DiGraph()
325
    G.add_node(0)
326
    G.add_edge(1, 2)
327
    H = nx.DiGraph()
328
    H.add_edge(3, 4)
329

    
330
    U = nx.full_join(G, H)
331
    assert_equal(set(U), set(G) | set(H))
332
    assert_equal(len(U), len(G) + len(H))
333
    assert_equal(len(U.edges()),
334
                 len(G.edges()) + len(H.edges()) + len(G)*len(H) * 2
335
                 )
336

    
337
    # DiGraphs Rename
338
    U = nx.full_join(G, H, rename=('g', 'h'))
339
    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
340
    assert_equal(len(U), len(G) + len(H))
341
    assert_equal(len(U.edges()),
342
                 len(G.edges()) + len(H.edges()) + len(G) * len(H) * 2
343
                 )
344

    
345

    
346
def test_full_join_multigraph():
347
    # MultiGraphs
348
    G = nx.MultiGraph()
349
    G.add_node(0)
350
    G.add_edge(1, 2)
351
    H = nx.MultiGraph()
352
    H.add_edge(3, 4)
353

    
354
    U = nx.full_join(G, H)
355
    assert_equal(set(U), set(G) | set(H))
356
    assert_equal(len(U), len(G) + len(H))
357
    assert_equal(len(U.edges()),
358
                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
359
                 )
360

    
361
    # MultiGraphs rename
362
    U = nx.full_join(G, H, rename=('g', 'h'))
363
    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
364
    assert_equal(len(U), len(G) + len(H))
365
    assert_equal(len(U.edges()),
366
                 len(G.edges()) + len(H.edges()) + len(G) * len(H)
367
                 )
368

    
369
    # MultiDiGraphs
370
    G = nx.MultiDiGraph()
371
    G.add_node(0)
372
    G.add_edge(1, 2)
373
    H = nx.MultiDiGraph()
374
    H.add_edge(3, 4)
375

    
376
    U = nx.full_join(G, H)
377
    assert_equal(set(U), set(G) | set(H))
378
    assert_equal(len(U), len(G) + len(H))
379
    assert_equal(len(U.edges()),
380
                 len(G.edges()) + len(H.edges()) + len(G) * len(H) * 2
381
                 )
382

    
383
    # MultiDiGraphs rename
384
    U = nx.full_join(G, H, rename=('g', 'h'))
385
    assert_equal(set(U), set(['g0', 'g1', 'g2', 'h3', 'h4']))
386
    assert_equal(len(U), len(G) + len(H))
387
    assert_equal(len(U.edges()),
388
                 len(G.edges()) + len(H.edges()) + len(G) * len(H) * 2
389
                 )
390

    
391

    
392
@raises(nx.NetworkXError)
393
def test_mixed_type_union():
394
    G = nx.Graph()
395
    H = nx.MultiGraph()
396
    U = nx.union(G, H)
397

    
398

    
399
@raises(nx.NetworkXError)
400
def test_mixed_type_disjoint_union():
401
    G = nx.Graph()
402
    H = nx.MultiGraph()
403
    U = nx.disjoint_union(G, H)
404

    
405

    
406
@raises(nx.NetworkXError)
407
def test_mixed_type_intersection():
408
    G = nx.Graph()
409
    H = nx.MultiGraph()
410
    U = nx.intersection(G, H)
411

    
412

    
413
@raises(nx.NetworkXError)
414
def test_mixed_type_difference():
415
    G = nx.Graph()
416
    H = nx.MultiGraph()
417
    U = nx.difference(G, H)
418

    
419

    
420
@raises(nx.NetworkXError)
421
def test_mixed_type_symmetric_difference():
422
    G = nx.Graph()
423
    H = nx.MultiGraph()
424
    U = nx.symmetric_difference(G, H)
425

    
426

    
427
@raises(nx.NetworkXError)
428
def test_mixed_type_compose():
429
    G = nx.Graph()
430
    H = nx.MultiGraph()
431
    U = nx.compose(G, H)