← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python-networkx/trusty

« back to all changes in this revision

Viewing changes to networkx/algorithms/tests/test_operators.py

  • Committer: Bazaar Package Importer
  • Author(s): Sandro Tosi
  • Date: 2010-12-10 23:50:27 UTC
  • mfrom: (1.2.4 upstream) (5.1.4 sid)
  • Revision ID: james.westby@ubuntu.com-20101210235027-b2supdwo0ad39d3s
Tags: 1.3-1
http://bugs.debian.org/567369
* New upstream release
* debian/patches/changeset_r1745.diff
  - dropped, available in upstream release
* debian/patches/10_doc_relocation
  - refreshed patch for new upstream code
* debian/control
  - upstream code is now compatible with 2.6 or later only
  - bump Standards-Version to 3.9.1 (no changes needed)
* debian/{control, rules}
  - run unittests at build time, b-d on python-nose added
* debian/copyright
  - removed reference to /usr/share/common-licenses/BSD
* Create a -doc package ; thanks to Yaroslav Halchenko for the report;
  Closes: #567369
  - (d/control) define a new binary package, and add depends on sphinx (>= 1)
  - (d/rules) build documentation, install it into the new -doc package
  - (d/patches/30_use_local_objects.inv) use local copy of remote objects.inv
* debian/{control, rules}
  - moved to dh7 and "reduced" rules file
* debian/rules
  - refer to built code when building doc
* debian/python-networkx-doc.doc-base
  - added doc-base information
* debian/patches/40_add_networkxcss
  - added as patch, since networkx.css is missing from the tarball, but needed
    to display properly HTML documentation
* debian/patches/50_boundary-test-fix.patch
  - upstream patch to restrict node boundary test cases to valid range
* debian/patches/60_remove_svn_refs.diff
  - upstream patch to remove references to old SVN repository (now Mercurial)
* debian/patches/70_set_matplotlib_ps_backend.patch
  - set matplotlib backend to 'PS', so a DISPLAY it's not required and the
    tests can be run in a "reduced" environment

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/tests/test_operators.py
 
1
 
 
2
import os, tempfile
 
3
from nose import SkipTest
 
4
from nose.tools import assert_raises, assert_true, assert_false, assert_equal
 
5
 
 
6
import networkx as nx
 
7
from networkx import *    
 
8
 
 
9
 
 
10
def test_union_attributes():
 
11
    g = nx.Graph()
 
12
    g.add_node(0, x=4)
 
13
    g.add_node(1, x=5)
 
14
    g.add_edge(0, 1, size=5)
 
15
    g.graph['name'] = 'g'
 
16
 
 
17
    h = g.copy()
 
18
    h.graph['name'] = 'h'
 
19
    h.graph['attr'] = 'attr'
 
20
    h.node[0]['x'] = 7
 
21
 
 
22
    gh = nx.union(g, h, rename=('g', 'h'))
 
23
    assert_equal( set(gh.nodes()) , set(['h0', 'h1', 'g0', 'g1']) )
 
24
    for n in gh:
 
25
        graph, node = n
 
26
        assert_equal( gh.node[n], eval(graph).node[int(node)] )
 
27
 
 
28
    assert_equal(gh.graph['attr'],'attr')
 
29
    assert_equal(gh.graph['name'],'g') # g graph attributes take precendent
 
30
 
 
31
def test_intersection():
 
32
    G=nx.Graph()
 
33
    H=nx.Graph()
 
34
    G.add_nodes_from([1,2,3,4])
 
35
    G.add_edge(1,2)
 
36
    G.add_edge(2,3)
 
37
    H.add_nodes_from([1,2,3,4])
 
38
    H.add_edge(2,3)
 
39
    H.add_edge(3,4)
 
40
    I=nx.intersection(G,H)
 
41
    assert_equal( set(I.nodes()) , set([1,2,3,4]) )    
 
42
    assert_equal( sorted(I.edges()) , [(2,3)] )    
 
43
 
 
44
 
 
45
def test_intersection_attributes():
 
46
    g = nx.Graph()
 
47
    g.add_node(0, x=4)
 
48
    g.add_node(1, x=5)
 
49
    g.add_edge(0, 1, size=5)
 
50
    g.graph['name'] = 'g'
 
51
 
 
52
    h = g.copy()
 
53
    h.graph['name'] = 'h'
 
54
    h.graph['attr'] = 'attr'
 
55
    h.node[0]['x'] = 7
 
56
 
 
57
    gh = nx.intersection(g, h)
 
58
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
 
59
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
 
60
    assert_equal( sorted(gh.edges()) , sorted(g.edges()) )
 
61
 
 
62
    h.remove_node(0)
 
63
    assert_raises(nx.NetworkXError, nx.intersection, g, h)
 
64
 
 
65
 
 
66
 
 
67
def test_intersection_multigraph_attributes():
 
68
    g = nx.MultiGraph()
 
69
    g.add_edge(0, 1, key=0)
 
70
    g.add_edge(0, 1, key=1)
 
71
    g.add_edge(0, 1, key=2)
 
72
    h = nx.MultiGraph()
 
73
    h.add_edge(0, 1, key=0)
 
74
    h.add_edge(0, 1, key=3)
 
75
    gh = nx.intersection(g, h)
 
76
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
 
77
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
 
78
    assert_equal( sorted(gh.edges()) , [(0,1)] )
 
79
    assert_equal( sorted(gh.edges(keys=True)) , [(0,1,0)] )
 
80
 
 
81
 
 
82
def test_difference():
 
83
    G=nx.Graph()
 
84
    H=nx.Graph()
 
85
    G.add_nodes_from([1,2,3,4])
 
86
    G.add_edge(1,2)
 
87
    G.add_edge(2,3)
 
88
    H.add_nodes_from([1,2,3,4])
 
89
    H.add_edge(2,3)
 
90
    H.add_edge(3,4)
 
91
    D=nx.difference(G,H)
 
92
    assert_equal( set(D.nodes()) , set([1,2,3,4]) )    
 
93
    assert_equal( sorted(D.edges()) , [(1,2)] )    
 
94
    D=nx.difference(H,G)
 
95
    assert_equal( set(D.nodes()) , set([1,2,3,4]) )    
 
96
    assert_equal( sorted(D.edges()) , [(3,4)] )    
 
97
    D=nx.symmetric_difference(G,H)
 
98
    assert_equal( set(D.nodes()) , set([1,2,3,4]) )    
 
99
    assert_equal( sorted(D.edges()) , [(1,2),(3,4)] )    
 
100
 
 
101
 
 
102
def test_difference_attributes():
 
103
    g = nx.Graph()
 
104
    g.add_node(0, x=4)
 
105
    g.add_node(1, x=5)
 
106
    g.add_edge(0, 1, size=5)
 
107
    g.graph['name'] = 'g'
 
108
 
 
109
    h = g.copy()
 
110
    h.graph['name'] = 'h'
 
111
    h.graph['attr'] = 'attr'
 
112
    h.node[0]['x'] = 7
 
113
 
 
114
    gh = nx.difference(g, h)
 
115
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
 
116
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
 
117
    assert_equal( sorted(gh.edges()) , [])
 
118
 
 
119
    h.remove_node(0)
 
120
    assert_raises(nx.NetworkXError, nx.intersection, g, h)
 
121
 
 
122
def test_difference_multigraph_attributes():
 
123
    g = nx.MultiGraph()
 
124
    g.add_edge(0, 1, key=0)
 
125
    g.add_edge(0, 1, key=1)
 
126
    g.add_edge(0, 1, key=2)
 
127
    h = nx.MultiGraph()
 
128
    h.add_edge(0, 1, key=0)
 
129
    h.add_edge(0, 1, key=3)
 
130
    gh = nx.difference(g, h)
 
131
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
 
132
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
 
133
    assert_equal( sorted(gh.edges()) , [(0,1)] )
 
134
    assert_equal( sorted(gh.edges(keys=True)) , [(0,1,3)] )
 
135
 
 
136
 
 
137
def test_symmetric_difference_multigraph():
 
138
    g = nx.MultiGraph()
 
139
    g.add_edge(0, 1, key=0)
 
140
    g.add_edge(0, 1, key=1)
 
141
    g.add_edge(0, 1, key=2)
 
142
    h = nx.MultiGraph()
 
143
    h.add_edge(0, 1, key=0)
 
144
    h.add_edge(0, 1, key=3)
 
145
    gh = nx.symmetric_difference(g, h)
 
146
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
 
147
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
 
148
    assert_equal( sorted(gh.edges()) , 3*[(0,1)] )
 
149
    assert_equal( sorted(sorted(e) for e in gh.edges(keys=True)), 
 
150
                  [[0,1,1],[0,1,2],[0,1,3]] )
 
151
 
 
152
def test_union_and_compose():
 
153
    K3=complete_graph(3)
 
154
    P3=path_graph(3)
 
155
 
 
156
    R=DiGraph()
 
157
    G1=DiGraph()
 
158
    G1.add_edge('A','B')
 
159
    G1.add_edge('A','C')
 
160
    G1.add_edge('A','D')
 
161
    G2=DiGraph()
 
162
    G2.add_edge(1,2)
 
163
    G2.add_edge(1,3)
 
164
    G2.add_edge(1,4)
 
165
 
 
166
    G=union(G1,G2,create_using=R)
 
167
    H=compose(G1,G2)
 
168
    assert_true(G.edges()==H.edges())
 
169
    assert_false(G.has_edge('A',1))
 
170
    assert_raises(nx.NetworkXError, nx.union, K3, P3)
 
171
    H1=union(H,G1,rename=('H','G1'))
 
172
    assert_equal(sorted(H1.nodes()),
 
173
                 ['G1A', 'G1B', 'G1C', 'G1D', 
 
174
                  'H1', 'H2', 'H3', 'H4', 'HA', 'HB', 'HC', 'HD'])
 
175
 
 
176
    H2=union(H,G2,rename=("H",""))
 
177
    assert_equal(sorted(H2.nodes()),
 
178
                 ['1', '2', '3', '4', 
 
179
                  'H1', 'H2', 'H3', 'H4', 'HA', 'HB', 'HC', 'HD'])
 
180
 
 
181
    assert_false(H1.has_edge('NB','NA'))
 
182
 
 
183
    G=compose(G,G)
 
184
    assert_equal(G.edges(),H.edges())
 
185
 
 
186
    G2=union(G2,G2,rename=('','copy'))
 
187
    assert_equal(sorted(G2.nodes()),
 
188
                 ['1', '2', '3', '4', 'copy1', 'copy2', 'copy3', 'copy4'])
 
189
 
 
190
    assert_equal(G2.neighbors('copy4'),[])
 
191
    assert_equal(sorted(G2.neighbors('copy1')),['copy2', 'copy3', 'copy4'])
 
192
    assert_equal(len(G),8)
 
193
    assert_equal(number_of_edges(G),6)
 
194
 
 
195
    E=disjoint_union(G,G)
 
196
    assert_equal(len(E),16)
 
197
    assert_equal(number_of_edges(E),12)
 
198
 
 
199
    E=disjoint_union(G1,G2)
 
200
    assert_equal(sorted(E.nodes()),[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
 
201
 
 
202
 
 
203
def test_union_multigraph():
 
204
    G=nx.MultiGraph()
 
205
    G.add_edge(1,2,key=0)
 
206
    G.add_edge(1,2,key=1)
 
207
    H=nx.MultiGraph()
 
208
    H.add_edge(3,4,key=0)
 
209
    H.add_edge(3,4,key=1)
 
210
    GH=nx.union(G,H)
 
211
    assert_equal( set(GH) , set(G)|set(H))
 
212
    assert_equal( set(GH.edges(keys=True)) , 
 
213
                  set(G.edges(keys=True))|set(H.edges(keys=True)))
 
214
 
 
215
def test_disjoint_union_multigraph():
 
216
    G=nx.MultiGraph()
 
217
    G.add_edge(0,1,key=0)
 
218
    G.add_edge(0,1,key=1)
 
219
    H=nx.MultiGraph()
 
220
    H.add_edge(2,3,key=0)
 
221
    H.add_edge(2,3,key=1)
 
222
    GH=nx.disjoint_union(G,H)
 
223
    assert_equal( set(GH) , set(G)|set(H))
 
224
    assert_equal( set(GH.edges(keys=True)) , 
 
225
                  set(G.edges(keys=True))|set(H.edges(keys=True)))
 
226
 
 
227
 
 
228
def test_complement():
 
229
    null=null_graph()
 
230
    empty1=empty_graph(1)
 
231
    empty10=empty_graph(10)
 
232
    K3=complete_graph(3)
 
233
    K5=complete_graph(5)
 
234
    K10=complete_graph(10)
 
235
    P2=path_graph(2)
 
236
    P3=path_graph(3)
 
237
    P5=path_graph(5)
 
238
    P10=path_graph(10)
 
239
    #complement of the complete graph is empty
 
240
 
 
241
    G=complement(K3)
 
242
    assert_true(is_isomorphic(G,empty_graph(3)))
 
243
    G=complement(K5)
 
244
    assert_true(is_isomorphic(G,empty_graph(5)))
 
245
    # for any G, G=complement(complement(G))
 
246
    P3cc=complement(complement(P3))
 
247
    assert_true(is_isomorphic(P3,P3cc))
 
248
    nullcc=complement(complement(null))
 
249
    assert_true(is_isomorphic(null,nullcc))
 
250
    b=bull_graph()
 
251
    bcc=complement(complement(b))
 
252
    assert_true(is_isomorphic(b,bcc))
 
253
 
 
254
def test_complement_2():
 
255
    G1=DiGraph()
 
256
    G1.add_edge('A','B')
 
257
    G1.add_edge('A','C')
 
258
    G1.add_edge('A','D')
 
259
    G1C=complement(G1)
 
260
    assert_equal(sorted(G1C.edges()),
 
261
                 [('B', 'A'), ('B', 'C'), 
 
262
                  ('B', 'D'), ('C', 'A'), ('C', 'B'), 
 
263
                  ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')])
 
264
 
 
265
 
 
266
def test_cartesian_product():
 
267
    null=null_graph()
 
268
    empty1=empty_graph(1)
 
269
    empty10=empty_graph(10)
 
270
    K3=complete_graph(3)
 
271
    K5=complete_graph(5)
 
272
    K10=complete_graph(10)
 
273
    P2=path_graph(2)
 
274
    P3=path_graph(3)
 
275
    P5=path_graph(5)
 
276
    P10=path_graph(10)
 
277
    # null graph
 
278
    G=cartesian_product(null,null)
 
279
    assert_true(is_isomorphic(G,null))
 
280
    # null_graph X anything = null_graph and v.v.
 
281
    G=cartesian_product(null,empty10)
 
282
    assert_true(is_isomorphic(G,null))
 
283
    G=cartesian_product(null,K3)
 
284
    assert_true(is_isomorphic(G,null))
 
285
    G=cartesian_product(null,K10)
 
286
    assert_true(is_isomorphic(G,null))
 
287
    G=cartesian_product(null,P3)
 
288
    assert_true(is_isomorphic(G,null))
 
289
    G=cartesian_product(null,P10)
 
290
    assert_true(is_isomorphic(G,null))
 
291
    G=cartesian_product(empty10,null)
 
292
    assert_true(is_isomorphic(G,null))
 
293
    G=cartesian_product(K3,null)
 
294
    assert_true(is_isomorphic(G,null))
 
295
    G=cartesian_product(K10,null)
 
296
    assert_true(is_isomorphic(G,null))
 
297
    G=cartesian_product(P3,null)
 
298
    assert_true(is_isomorphic(G,null))
 
299
    G=cartesian_product(P10,null)
 
300
    assert_true(is_isomorphic(G,null))
 
301
 
 
302
    # order(GXH)=order(G)*order(H)
 
303
    G=cartesian_product(P5,K3)
 
304
    assert_equal(number_of_nodes(G),5*3)
 
305
    assert_equal(number_of_edges(G),
 
306
                 number_of_edges(P5)*number_of_nodes(K3)+
 
307
                 number_of_edges(K3)*number_of_nodes(P5))
 
308
    G=cartesian_product(K3,K5)
 
309
    assert_equal(number_of_nodes(G),3*5)
 
310
    assert_equal(number_of_edges(G),
 
311
                 number_of_edges(K5)*number_of_nodes(K3)+
 
312
                 number_of_edges(K3)*number_of_nodes(K5))
 
313
 
 
314
    # test some classic product graphs
 
315
    # cube = 2-path X 2-path
 
316
    G=cartesian_product(P2,P2)
 
317
    G=cartesian_product(P2,G)
 
318
    assert_true(is_isomorphic(G,cubical_graph()))
 
319
 
 
320
    # 3x3 grid
 
321
    G=cartesian_product(P3,P3)
 
322
    assert_true(is_isomorphic(G,grid_2d_graph(3,3)))
 
323
 
 
324
 
 
325
def test_cartesian_product_multigraph():
 
326
    G=nx.MultiGraph()
 
327
    G.add_edge(1,2,key=0)
 
328
    G.add_edge(1,2,key=1)
 
329
    H=nx.MultiGraph()
 
330
    H.add_edge(3,4,key=0)
 
331
    H.add_edge(3,4,key=1)
 
332
    GH=nx.cartesian_product(G,H)
 
333
    assert_equal( set(GH) , set([(1, 3), (2, 3), (2, 4), (1, 4)]))
 
334
    assert_equal( set(GH.edges(keys=True)) ,
 
335
                  set([((1, 3), (2, 3), 0), ((1, 3), (2, 3), 1), 
 
336
                       ((1, 3), (1, 4), 0), ((1, 3), (1, 4), 1), 
 
337
                       ((2, 3), (2, 4), 0), ((2, 3), (2, 4), 1), 
 
338
                       ((2, 4), (1, 4), 0), ((2, 4), (1, 4), 1)]))
 
339
 
 
340
def test_compose_multigraph():
 
341
    G=nx.MultiGraph()
 
342
    G.add_edge(1,2,key=0)
 
343
    G.add_edge(1,2,key=1)
 
344
    H=nx.MultiGraph()
 
345
    H.add_edge(3,4,key=0)
 
346
    H.add_edge(3,4,key=1)
 
347
    GH=nx.compose(G,H)
 
348
    assert_equal( set(GH) , set(G)|set(H))
 
349
    assert_equal( set(GH.edges(keys=True)) , 
 
350
                  set(G.edges(keys=True))|set(H.edges(keys=True)))
 
351
    H.add_edge(1,2,key=2)
 
352
    GH=nx.compose(G,H)
 
353
    assert_equal( set(GH) , set(G)|set(H))
 
354
    assert_equal( set(GH.edges(keys=True)) , 
 
355
                  set(G.edges(keys=True))|set(H.edges(keys=True)))