1 #!/usr/bin/env python 2 """Original NetworkX graph tests""" 3 from nose.tools import * 4 import networkx 5 import networkx as nx 6 from networkx import convert_node_labels_to_integers as cnlti 7 from networkx.testing import * 8 9 class HistoricalTests(object): 10 11 def setUp(self): 12 self.null=nx.null_graph() 13 self.P1=cnlti(nx.path_graph(1),first_label=1) 14 self.P3=cnlti(nx.path_graph(3),first_label=1) 15 self.P10=cnlti(nx.path_graph(10),first_label=1) 16 self.K1=cnlti(nx.complete_graph(1),first_label=1) 17 self.K3=cnlti(nx.complete_graph(3),first_label=1) 18 self.K4=cnlti(nx.complete_graph(4),first_label=1) 19 self.K5=cnlti(nx.complete_graph(5),first_label=1) 20 self.K10=cnlti(nx.complete_graph(10),first_label=1) 21 self.G=nx.Graph 22 23 def test_name(self): 24 G=self.G(name="test") 25 assert_equal(str(G),'test') 26 assert_equal(G.name,'test') 27 H=self.G() 28 assert_equal(H.name,'') 29 30 # Nodes 31 32 def test_add_remove_node(self): 33 G=self.G() 34 G.add_node('A') 35 assert_true(G.has_node('A')) 36 G.remove_node('A') 37 assert_false(G.has_node('A')) 38 39 def test_nonhashable_node(self): 40 # Test if a non-hashable object is in the Graph. A python dict will 41 # raise a TypeError, but for a Graph class a simple False should be 42 # returned (see Graph __contains__). If it cannot be a node then it is 43 # not a node. 44 G=self.G() 45 assert_false(G.has_node(['A'])) 46 assert_false(G.has_node({'A':1})) 47 48 def test_add_nodes_from(self): 49 G=self.G() 50 G.add_nodes_from(list("ABCDEFGHIJKL")) 51 assert_true(G.has_node("L")) 52 G.remove_nodes_from(['H','I','J','K','L']) 53 G.add_nodes_from([1,2,3,4]) 54 assert_equal(sorted(G.nodes(),key=str), 55 [1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F', 'G']) 56 # test __iter__ 57 assert_equal(sorted(G,key=str), 58 [1, 2, 3, 4, 'A', 'B', 'C', 'D', 'E', 'F', 'G']) 59 60 61 def test_contains(self): 62 G=self.G() 63 G.add_node('A') 64 assert_true('A' in G) 65 assert_false([] in G) # never raise a Key or TypeError in this test 66 assert_false({1:1} in G) 67 68 def test_add_remove(self): 69 # Test add_node and remove_node acting for various nbunch 70 G=self.G() 71 G.add_node('m') 72 assert_true(G.has_node('m')) 73 G.add_node('m') # no complaints 74 assert_raises(nx.NetworkXError,G.remove_node,'j') 75 G.remove_node('m') 76 assert_equal(G.nodes(),[]) 77 78 def test_nbunch_is_list(self): 79 G=self.G() 80 G.add_nodes_from(list("ABCD")) 81 G.add_nodes_from(self.P3) # add nbunch of nodes (nbunch=Graph) 82 assert_equal(sorted(G.nodes(),key=str), 83 [1, 2, 3, 'A', 'B', 'C', 'D']) 84 G.remove_nodes_from(self.P3) # remove nbunch of nodes (nbunch=Graph) 85 assert_equal(sorted(G.nodes(),key=str), 86 ['A', 'B', 'C', 'D']) 87 88 def test_nbunch_is_set(self): 89 G=self.G() 90 nbunch=set("ABCDEFGHIJKL") 91 G.add_nodes_from(nbunch) 92 assert_true(G.has_node("L")) 93 94 def test_nbunch_dict(self): 95 # nbunch is a dict with nodes as keys 96 G=self.G() 97 nbunch=set("ABCDEFGHIJKL") 98 G.add_nodes_from(nbunch) 99 nbunch={'I':"foo",'J':2,'K':True,'L':"spam"} 100 G.remove_nodes_from(nbunch) 101 assert_true(sorted(G.nodes(),key=str), 102 ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) 103 104 def test_nbunch_iterator(self): 105 G=self.G() 106 G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) 107 n_iter=self.P3.nodes_iter() 108 G.add_nodes_from(n_iter) 109 assert_equal(sorted(G.nodes(),key=str), 110 [1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) 111 n_iter=self.P3.nodes_iter() # rebuild same iterator 112 G.remove_nodes_from(n_iter) # remove nbunch of nodes (nbunch=iterator) 113 assert_equal(sorted(G.nodes(),key=str), 114 ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) 115 116 def test_nbunch_graph(self): 117 G=self.G() 118 G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) 119 nbunch=self.K3 120 G.add_nodes_from(nbunch) 121 assert_true(sorted(G.nodes(),key=str), 122 [1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) 123 124 125 126 # Edges 127 128 def test_add_edge(self): 129 G=self.G() 130 assert_raises(TypeError,G.add_edge,'A') 131 132 G.add_edge('A','B') # testing add_edge() 133 G.add_edge('A','B') # should fail silently 134 assert_true(G.has_edge('A','B')) 135 assert_false(G.has_edge('A','C')) 136 assert_true(G.has_edge( *('A','B') )) 137 if G.is_directed(): 138 assert_false(G.has_edge('B','A')) 139 else: 140 # G is undirected, so B->A is an edge 141 assert_true(G.has_edge('B','A')) 142 143 144 G.add_edge('A','C') # test directedness 145 G.add_edge('C','A') 146 G.remove_edge('C','A') 147 if G.is_directed(): 148 assert_true(G.has_edge('A','C')) 149 else: 150 assert_false(G.has_edge('A','C')) 151 assert_false(G.has_edge('C','A')) 152 153 154 def test_self_loop(self): 155 G=self.G() 156 G.add_edge('A','A') # test self loops 157 assert_true(G.has_edge('A','A')) 158 G.remove_edge('A','A') 159 G.add_edge('X','X') 160 assert_true(G.has_node('X')) 161 G.remove_node('X') 162 G.add_edge('A','Z') # should add the node silently 163 assert_true(G.has_node('Z')) 164 165 def test_add_edges_from(self): 166 G=self.G() 167 G.add_edges_from([('B','C')]) # test add_edges_from() 168 assert_true(G.has_edge('B','C')) 169 if G.is_directed(): 170 assert_false(G.has_edge('C','B')) 171 else: 172 assert_true(G.has_edge('C','B')) # undirected 173 174 G.add_edges_from([('D','F'),('B','D')]) 175 assert_true(G.has_edge('D','F')) 176 assert_true(G.has_edge('B','D')) 177 178 if G.is_directed(): 179 assert_false(G.has_edge('D','B')) 180 else: 181 assert_true(G.has_edge('D','B')) # undirected 182 183 def test_add_edges_from2(self): 184 G=self.G() 185 # after failing silently, should add 2nd edge 186 G.add_edges_from([tuple('IJ'),list('KK'),tuple('JK')]) 187 assert_true(G.has_edge(*('I','J'))) 188 assert_true(G.has_edge(*('K','K'))) 189 assert_true(G.has_edge(*('J','K'))) 190 if G.is_directed(): 191 assert_false(G.has_edge(*('K','J'))) 192 else: 193 assert_true(G.has_edge(*('K','J'))) 194 195 def test_add_edges_from3(self): 196 G=self.G() 197 G.add_edges_from(zip(list('ACD'),list('CDE'))) 198 assert_true(G.has_edge('D','E')) 199 assert_false(G.has_edge('E','C')) 200 201 def test_remove_edge(self): 202 G=self.G() 203 G.add_nodes_from([1, 2, 3, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']) 204 205 G.add_edges_from(zip(list('MNOP'),list('NOPM'))) 206 assert_true(G.has_edge('O','P')) 207 assert_true( G.has_edge('P','M')) 208 G.remove_node('P') # tests remove_node()'s handling of edges. 209 assert_false(G.has_edge('P','M')) 210 assert_raises(TypeError,G.remove_edge,'M') 211 212 G.add_edge('N','M') 213 assert_true(G.has_edge('M','N')) 214 G.remove_edge('M','N') 215 assert_false(G.has_edge('M','N')) 216 217 # self loop fails silently 218 G.remove_edges_from([list('HI'),list('DF'), 219 tuple('KK'),tuple('JK')]) 220 assert_false(G.has_edge('H','I')) 221 assert_false(G.has_edge('J','K')) 222 G.remove_edges_from([list('IJ'),list('KK'),list('JK')]) 223 assert_false(G.has_edge('I','J')) 224 G.remove_nodes_from(set('ZEFHIMNO')) 225 G.add_edge('J','K') 226 227 228 def test_edges_nbunch(self): 229 # Test G.edges(nbunch) with various forms of nbunch 230 G=self.G() 231 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 232 ('C', 'B'), ('C', 'D')]) 233 # node not in nbunch should be quietly ignored 234 assert_raises(nx.NetworkXError,G.edges,6) 235 assert_equals(G.edges('Z'),[]) # iterable non-node 236 # nbunch can be an empty list 237 assert_equals(G.edges([]),[]) 238 if G.is_directed(): 239 elist=[('A', 'B'), ('A', 'C'), ('B', 'D')] 240 else: 241 elist=[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')] 242 # nbunch can be a list 243 assert_edges_equal(G.edges(['A','B']),elist) 244 # nbunch can be a set 245 assert_edges_equal(G.edges(set(['A','B'])),elist) 246 # nbunch can be a graph 247 G1=self.G() 248 G1.add_nodes_from('AB') 249 assert_edges_equal(G.edges(G1),elist) 250 # nbunch can be a dict with nodes as keys 251 ndict={'A': "thing1", 'B': "thing2"} 252 assert_edges_equal(G.edges(ndict),elist) 253 # nbunch can be a single node 254 assert_edges_equal(G.edges('A'), [('A', 'B'), ('A', 'C')]) 255 256 assert_edges_equal(G.nodes_iter(), ['A', 'B', 'C', 'D']) 257 258 def test_edges_iter_nbunch(self): 259 G=self.G() 260 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 261 ('C', 'B'), ('C', 'D')]) 262 # Test G.edges_iter(nbunch) with various forms of nbunch 263 # node not in nbunch should be quietly ignored 264 assert_equals(list(G.edges_iter('Z')),[]) 265 # nbunch can be an empty list 266 assert_equals(sorted(G.edges_iter([])),[]) 267 if G.is_directed(): 268 elist=[('A', 'B'), ('A', 'C'), ('B', 'D')] 269 else: 270 elist=[('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')] 271 # nbunch can be a list 272 assert_edges_equal(G.edges_iter(['A','B']),elist) 273 # nbunch can be a set 274 assert_edges_equal(G.edges_iter(set(['A','B'])),elist) 275 # nbunch can be a graph 276 G1=self.G() 277 G1.add_nodes_from(['A','B']) 278 assert_edges_equal(G.edges_iter(G1),elist) 279 # nbunch can be a dict with nodes as keys 280 ndict={'A': "thing1", 'B': "thing2"} 281 assert_edges_equal(G.edges_iter(ndict),elist) 282 # nbunch can be a single node 283 assert_edges_equal(G.edges_iter('A'), [('A', 'B'), ('A', 'C')]) 284 285 # nbunch can be nothing (whole graph) 286 assert_edges_equal(G.edges_iter(), [('A', 'B'), ('A', 'C'), ('B', 'D'), 287 ('C', 'B'), ('C', 'D')]) 288 289 290 def test_degree(self): 291 G=self.G() 292 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 293 ('C', 'B'), ('C', 'D')]) 294 assert_equal(G.degree('A'),2) 295 296 # degree of single node in iterable container must return dict 297 assert_equal(list(G.degree(['A']).values()),[2]) 298 assert_equal(G.degree(['A']),{'A': 2}) 299 assert_equal(sorted(G.degree(['A','B']).values()),[2, 3]) 300 assert_equal(G.degree(['A','B']),{'A': 2, 'B': 3}) 301 assert_equal(sorted(G.degree().values()),[2, 2, 3, 3]) 302 assert_equal(sorted([v for k,v in G.degree_iter()]), 303 [2, 2, 3, 3]) 304 305 def test_degree2(self): 306 H=self.G() 307 H.add_edges_from([(1,24),(1,2)]) 308 assert_equal(sorted(H.degree([1,24]).values()),[1, 2]) 309 310 def test_degree_graph(self): 311 P3=nx.path_graph(3) 312 P5=nx.path_graph(5) 313 # silently ignore nodes not in P3 314 assert_equal(P3.degree(['A','B']),{}) 315 # nbunch can be a graph 316 assert_equal(sorted(P5.degree(P3).values()),[1, 2, 2]) 317 # nbunch can be a graph thats way to big 318 assert_equal(sorted(P3.degree(P5).values()),[1, 1, 2]) 319 assert_equal(P5.degree([]),{}) 320 assert_equal(list(P5.degree_iter([])),[]) 321 assert_equal(dict(P5.degree_iter([])),{}) 322 323 def test_null(self): 324 null=nx.null_graph() 325 assert_equal(null.degree(),{}) 326 assert_equal(list(null.degree_iter()),[]) 327 assert_equal(dict(null.degree_iter()),{}) 328 329 def test_order_size(self): 330 G=self.G() 331 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 332 ('C', 'B'), ('C', 'D')]) 333 assert_equal(G.order(),4) 334 assert_equal(G.size(),5) 335 assert_equal(G.number_of_edges(),5) 336 assert_equal(G.number_of_edges('A','B'),1) 337 assert_equal(G.number_of_edges('A','D'),0) 338 339 def test_copy(self): 340 G=self.G() 341 H=G.copy() # copy 342 assert_equal(H.adj,G.adj) 343 assert_equal(H.name,G.name) 344 assert_not_equal(H,G) 345 346 def test_subgraph(self): 347 G=self.G() 348 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 349 ('C', 'B'), ('C', 'D')]) 350 SG=G.subgraph(['A','B','D']) 351 assert_nodes_equal(SG.nodes(),['A', 'B', 'D']) 352 assert_edges_equal(SG.edges(),[('A', 'B'), ('B', 'D')]) 353 354 def test_to_directed(self): 355 G=self.G() 356 if not G.is_directed(): 357 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 358 ('C', 'B'), ('C', 'D')]) 359 360 DG=G.to_directed() 361 assert_not_equal(DG,G) # directed copy or copy 362 363 assert_true(DG.is_directed()) 364 assert_equal(DG.name,G.name) 365 assert_equal(DG.adj,G.adj) 366 assert_equal(sorted(DG.out_edges(list('AB'))), 367 [('A', 'B'), ('A', 'C'), ('B', 'A'), 368 ('B', 'C'), ('B', 'D')]) 369 DG.remove_edge('A','B') 370 assert_true(DG.has_edge('B','A')) # this removes B-A but not A-B 371 assert_false(DG.has_edge('A','B')) 372 373 def test_to_undirected(self): 374 G=self.G() 375 if G.is_directed(): 376 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 377 ('C', 'B'), ('C', 'D')]) 378 UG=G.to_undirected() # to_undirected 379 assert_not_equal(UG,G) 380 assert_false(UG.is_directed()) 381 assert_true(G.is_directed()) 382 assert_equal(UG.name,G.name) 383 assert_not_equal(UG.adj,G.adj) 384 assert_equal(sorted(UG.edges(list('AB'))), 385 [('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]) 386 assert_equal(sorted(UG.edges(['A','B'])), 387 [('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D')]) 388 UG.remove_edge('A','B') 389 assert_false(UG.has_edge('B','A')) 390 assert_false( UG.has_edge('A','B')) 391 392 393 394 def test_neighbors(self): 395 G=self.G() 396 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 397 ('C', 'B'), ('C', 'D')]) 398 G.add_nodes_from('GJK') 399 assert_equal(sorted(G['A']),['B', 'C']) 400 assert_equal(sorted(G.neighbors('A')),['B', 'C']) 401 assert_equal(sorted(G.neighbors_iter('A')),['B', 'C']) 402 assert_equal(sorted(G.neighbors('G')),[]) 403 assert_raises(nx.NetworkXError,G.neighbors,'j') 404 405 def test_iterators(self): 406 G=self.G() 407 G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), 408 ('C', 'B'), ('C', 'D')]) 409 G.add_nodes_from('GJK') 410 assert_equal(sorted(G.nodes_iter()), 411 ['A', 'B', 'C', 'D', 'G', 'J', 'K']) 412 assert_edges_equal(G.edges_iter(), 413 [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'B'), ('C', 'D')]) 414 415 assert_equal(sorted([v for k,v in G.degree_iter()]), 416 [0, 0, 0, 2, 2, 3, 3]) 417 assert_equal(sorted(G.degree_iter(),key=str), 418 [('A', 2), ('B', 3), ('C', 3), ('D', 2), 419 ('G', 0), ('J', 0), ('K', 0)]) 420 assert_equal(sorted(G.neighbors_iter('A')),['B', 'C']) 421 assert_raises(nx.NetworkXError,G.neighbors_iter,'X') 422 G.clear() 423 assert_equal(nx.number_of_nodes(G),0) 424 assert_equal(nx.number_of_edges(G),0) 425 426 427 def test_null_subgraph(self): 428 # Subgraph of a null graph is a null graph 429 nullgraph=nx.null_graph() 430 G=nx.null_graph() 431 H=G.subgraph([]) 432 assert_true(nx.is_isomorphic(H,nullgraph)) 433 434 def test_empty_subgraph(self): 435 # Subgraph of an empty graph is an empty graph. test 1 436 nullgraph=nx.null_graph() 437 E5=nx.empty_graph(5) 438 E10=nx.empty_graph(10) 439 H=E10.subgraph([]) 440 assert_true(nx.is_isomorphic(H,nullgraph)) 441 H=E10.subgraph([1,2,3,4,5]) 442 assert_true(nx.is_isomorphic(H,E5)) 443 444 def test_complete_subgraph(self): 445 # Subgraph of a complete graph is a complete graph 446 K1=nx.complete_graph(1) 447 K3=nx.complete_graph(3) 448 K5=nx.complete_graph(5) 449 H=K5.subgraph([1,2,3]) 450 assert_true(nx.is_isomorphic(H,K3)) 451 452 def test_subgraph_nbunch(self): 453 nullgraph=nx.null_graph() 454 K1=nx.complete_graph(1) 455 K3=nx.complete_graph(3) 456 K5=nx.complete_graph(5) 457 # Test G.subgraph(nbunch), where nbunch is a single node 458 H=K5.subgraph(1) 459 assert_true(nx.is_isomorphic(H,K1)) 460 # Test G.subgraph(nbunch), where nbunch is a set 461 H=K5.subgraph(set([1])) 462 assert_true(nx.is_isomorphic(H,K1)) 463 # Test G.subgraph(nbunch), where nbunch is an iterator 464 H=K5.subgraph(iter(K3)) 465 assert_true(nx.is_isomorphic(H,K3)) 466 # Test G.subgraph(nbunch), where nbunch is another graph 467 H=K5.subgraph(K3) 468 assert_true(nx.is_isomorphic(H,K3)) 469 H=K5.subgraph([9]) 470 assert_true(nx.is_isomorphic(H,nullgraph)) 471 472 def test_node_tuple_error(self): 473 H=self.G() 474 # Test error handling of tuple as a node 475 assert_raises(nx.NetworkXError,H.remove_node,(1,2)) 476 H.remove_nodes_from([(1,2)]) # no error 477 assert_raises(nx.NetworkXError,H.neighbors,(1,2)) 478
