1import unittest 2 3from altgraph import GraphError 4from altgraph.Graph import Graph 5 6class TestGraph (unittest.TestCase): 7 8 def test_nodes(self): 9 graph = Graph() 10 11 self.assertEqual(graph.node_list(), []) 12 13 o1 = object() 14 o1b = object() 15 o2 = object() 16 graph.add_node(1, o1) 17 graph.add_node(1, o1b) 18 graph.add_node(2, o2) 19 graph.add_node(3) 20 21 self.assertRaises(TypeError, graph.add_node, []) 22 23 self.assertTrue(graph.node_data(1) is o1) 24 self.assertTrue(graph.node_data(2) is o2) 25 self.assertTrue(graph.node_data(3) is None) 26 27 self.assertTrue(1 in graph) 28 self.assertTrue(2 in graph) 29 self.assertTrue(3 in graph) 30 31 self.assertEqual(graph.number_of_nodes(), 3) 32 self.assertEqual(graph.number_of_hidden_nodes(), 0) 33 self.assertEqual(graph.hidden_node_list(), []) 34 self.assertEqual(list(sorted(graph)), [1, 2, 3]) 35 36 graph.hide_node(1) 37 graph.hide_node(2) 38 graph.hide_node(3) 39 40 41 self.assertEqual(graph.number_of_nodes(), 0) 42 self.assertEqual(graph.number_of_hidden_nodes(), 3) 43 self.assertEqual(list(sorted(graph.hidden_node_list())), [1, 2, 3]) 44 45 self.assertFalse(1 in graph) 46 self.assertFalse(2 in graph) 47 self.assertFalse(3 in graph) 48 49 graph.add_node(1) 50 self.assertFalse(1 in graph) 51 52 graph.restore_node(1) 53 self.assertTrue(1 in graph) 54 self.assertFalse(2 in graph) 55 self.assertFalse(3 in graph) 56 57 graph.restore_all_nodes() 58 self.assertTrue(1 in graph) 59 self.assertTrue(2 in graph) 60 self.assertTrue(3 in graph) 61 62 self.assertEqual(list(sorted(graph.node_list())), [1, 2, 3]) 63 64 v = graph.describe_node(1) 65 self.assertEqual(v, (1, o1, [], [])) 66 67 def test_edges(self): 68 graph = Graph() 69 graph.add_node(1) 70 graph.add_node(2) 71 graph.add_node(3) 72 graph.add_node(4) 73 graph.add_node(5) 74 75 self.assertTrue(isinstance(graph.edge_list(), list)) 76 77 graph.add_edge(1, 2) 78 graph.add_edge(4, 5, 'a') 79 80 self.assertRaises(GraphError, graph.add_edge, 'a', 'b', create_nodes=False) 81 82 self.assertEqual(graph.number_of_hidden_edges(), 0) 83 self.assertEqual(graph.number_of_edges(), 2) 84 e = graph.edge_by_node(1, 2) 85 self.assertTrue(isinstance(e, int)) 86 graph.hide_edge(e) 87 self.assertEqual(graph.number_of_hidden_edges(), 1) 88 self.assertEqual(graph.number_of_edges(), 1) 89 e2 = graph.edge_by_node(1, 2) 90 self.assertTrue(e2 is None) 91 92 graph.restore_edge(e) 93 e2 = graph.edge_by_node(1, 2) 94 self.assertEqual(e, e2) 95 self.assertEqual(graph.number_of_hidden_edges(), 0) 96 97 self.assertEqual(graph.number_of_edges(), 2) 98 99 e1 = graph.edge_by_node(1, 2) 100 e2 = graph.edge_by_node(4, 5) 101 graph.hide_edge(e1) 102 graph.hide_edge(e2) 103 104 self.assertEqual(graph.number_of_edges(), 0) 105 graph.restore_all_edges() 106 self.assertEqual(graph.number_of_edges(), 2) 107 108 self.assertEqual(graph.edge_by_id(e1), (1,2)) 109 self.assertRaises(GraphError, graph.edge_by_id, (e1+1)*(e2+1)+1) 110 111 self.assertEqual(list(sorted(graph.edge_list())), [e1, e2]) 112 113 self.assertEqual(graph.describe_edge(e1), (e1, 1, 1, 2)) 114 self.assertEqual(graph.describe_edge(e2), (e2, 'a', 4, 5)) 115 116 self.assertEqual(graph.edge_data(e1), 1) 117 self.assertEqual(graph.edge_data(e2), 'a') 118 119 self.assertEqual(graph.head(e2), 4) 120 self.assertEqual(graph.tail(e2), 5) 121 122 graph.add_edge(1, 3) 123 graph.add_edge(1, 5) 124 graph.add_edge(4, 1) 125 126 self.assertEqual(list(sorted(graph.out_nbrs(1))), [2, 3, 5]) 127 self.assertEqual(list(sorted(graph.inc_nbrs(1))), [4]) 128 self.assertEqual(list(sorted(graph.inc_nbrs(5))), [1, 4]) 129 self.assertEqual(list(sorted(graph.all_nbrs(1))), [2, 3, 4, 5]) 130 131 graph.add_edge(5, 1) 132 self.assertEqual(list(sorted(graph.all_nbrs(5))), [1, 4]) 133 134 self.assertEqual(graph.out_degree(1), 3) 135 self.assertEqual(graph.inc_degree(2), 1) 136 self.assertEqual(graph.inc_degree(5), 2) 137 self.assertEqual(graph.all_degree(5), 3) 138 139 v = graph.out_edges(4) 140 self.assertTrue(isinstance(v, list)) 141 self.assertEqual(graph.edge_by_id(v[0]), (4, 5)) 142 143 v = graph.out_edges(1) 144 for e in v: 145 self.assertEqual(graph.edge_by_id(e)[0], 1) 146 147 v = graph.inc_edges(1) 148 self.assertTrue(isinstance(v, list)) 149 self.assertEqual(graph.edge_by_id(v[0]), (4, 1)) 150 151 v = graph.inc_edges(5) 152 for e in v: 153 self.assertEqual(graph.edge_by_id(e)[1], 5) 154 155 v = graph.all_edges(5) 156 for e in v: 157 self.assertTrue(graph.edge_by_id(e)[1] == 5 or graph.edge_by_id(e)[0] == 5) 158 159 e1 = graph.edge_by_node(1, 2) 160 self.assertTrue(isinstance(e1, int)) 161 graph.hide_node(1) 162 self.assertRaises(GraphError, graph.edge_by_node, 1, 2) 163 graph.restore_node(1) 164 e2 = graph.edge_by_node(1, 2) 165 self.assertEqual(e1, e2) 166 167 168 169 def test_toposort(self): 170 graph = Graph() 171 graph.add_node(1) 172 graph.add_node(2) 173 graph.add_node(3) 174 graph.add_node(4) 175 graph.add_node(5) 176 177 graph.add_edge(1, 2) 178 graph.add_edge(1, 3) 179 graph.add_edge(2, 4) 180 graph.add_edge(3, 5) 181 182 ok, result = graph.forw_topo_sort() 183 self.assertTrue(ok) 184 for idx in range(1, 6): 185 self.assertTrue(idx in result) 186 187 self.assertTrue(result.index(1) < result.index(2)) 188 self.assertTrue(result.index(1) < result.index(3)) 189 self.assertTrue(result.index(2) < result.index(4)) 190 self.assertTrue(result.index(3) < result.index(5)) 191 192 ok, result = graph.back_topo_sort() 193 self.assertTrue(ok) 194 for idx in range(1, 6): 195 self.assertTrue(idx in result) 196 self.assertTrue(result.index(2) < result.index(1)) 197 self.assertTrue(result.index(3) < result.index(1)) 198 self.assertTrue(result.index(4) < result.index(2)) 199 self.assertTrue(result.index(5) < result.index(3)) 200 201 202 # Same graph as before, but with edges 203 # reversed, which means we should get 204 # the same results as before if using 205 # back_topo_sort rather than forw_topo_sort 206 # (and v.v.) 207 208 graph = Graph() 209 graph.add_node(1) 210 graph.add_node(2) 211 graph.add_node(3) 212 graph.add_node(4) 213 graph.add_node(5) 214 215 graph.add_edge(2, 1) 216 graph.add_edge(3, 1) 217 graph.add_edge(4, 2) 218 graph.add_edge(5, 3) 219 220 ok, result = graph.back_topo_sort() 221 self.assertTrue(ok) 222 for idx in range(1, 6): 223 self.assertTrue(idx in result) 224 225 self.assertTrue(result.index(1) < result.index(2)) 226 self.assertTrue(result.index(1) < result.index(3)) 227 self.assertTrue(result.index(2) < result.index(4)) 228 self.assertTrue(result.index(3) < result.index(5)) 229 230 ok, result = graph.forw_topo_sort() 231 self.assertTrue(ok) 232 for idx in range(1, 6): 233 self.assertTrue(idx in result) 234 self.assertTrue(result.index(2) < result.index(1)) 235 self.assertTrue(result.index(3) < result.index(1)) 236 self.assertTrue(result.index(4) < result.index(2)) 237 self.assertTrue(result.index(5) < result.index(3)) 238 239 240 # Create a cycle 241 graph.add_edge(1, 5) 242 ok, result = graph.forw_topo_sort() 243 self.assertFalse(ok) 244 ok, result = graph.back_topo_sort() 245 self.assertFalse(ok) 246 247 def test_bfs_subgraph(self): 248 graph = Graph() 249 graph.add_edge(1, 2) 250 graph.add_edge(1, 4) 251 graph.add_edge(2, 4) 252 graph.add_edge(4, 8) 253 graph.add_edge(4, 9) 254 graph.add_edge(4, 10) 255 graph.add_edge(8, 10) 256 257 subgraph = graph.forw_bfs_subgraph(10) 258 self.assertTrue(isinstance(subgraph, Graph)) 259 self.assertEqual(subgraph.number_of_nodes(), 1) 260 self.assertTrue(10 in subgraph) 261 self.assertEqual(subgraph.number_of_edges(), 0) 262 263 subgraph = graph.forw_bfs_subgraph(4) 264 self.assertTrue(isinstance(subgraph, Graph)) 265 self.assertEqual(subgraph.number_of_nodes(), 4) 266 self.assertTrue(4 in subgraph) 267 self.assertTrue(8 in subgraph) 268 self.assertTrue(9 in subgraph) 269 self.assertTrue(10 in subgraph) 270 self.assertEqual(subgraph.number_of_edges(), 4) 271 e = subgraph.edge_by_node(4, 8) 272 e = subgraph.edge_by_node(4, 9) 273 e = subgraph.edge_by_node(4, 10) 274 e = subgraph.edge_by_node(8, 10) 275 276 # same graph as before, but switch around 277 # edges. This results in the same test results 278 # but now for back_bfs_subgraph rather than 279 # forw_bfs_subgraph 280 281 graph = Graph() 282 graph.add_edge(2, 1) 283 graph.add_edge(4, 1) 284 graph.add_edge(4, 2) 285 graph.add_edge(8, 4) 286 graph.add_edge(9, 4) 287 graph.add_edge(10, 4) 288 graph.add_edge(10, 8) 289 290 subgraph = graph.back_bfs_subgraph(10) 291 self.assertTrue(isinstance(subgraph, Graph)) 292 self.assertEqual(subgraph.number_of_nodes(), 1) 293 self.assertTrue(10 in subgraph) 294 self.assertEqual(subgraph.number_of_edges(), 0) 295 296 subgraph = graph.back_bfs_subgraph(4) 297 self.assertTrue(isinstance(subgraph, Graph)) 298 self.assertEqual(subgraph.number_of_nodes(), 4) 299 self.assertTrue(4 in subgraph) 300 self.assertTrue(8 in subgraph) 301 self.assertTrue(9 in subgraph) 302 self.assertTrue(10 in subgraph) 303 self.assertEqual(subgraph.number_of_edges(), 4) 304 e = subgraph.edge_by_node(4, 8) 305 e = subgraph.edge_by_node(4, 9) 306 e = subgraph.edge_by_node(4, 10) 307 e = subgraph.edge_by_node(8, 10) 308 309 def test_iterdfs(self): 310 graph = Graph() 311 graph.add_edge("1", "1.1") 312 graph.add_edge("1", "1.2") 313 graph.add_edge("1", "1.3") 314 graph.add_edge("1.1", "1.1.1") 315 graph.add_edge("1.1", "1.1.2") 316 graph.add_edge("1.2", "1.2.1") 317 graph.add_edge("1.2", "1.2.2") 318 graph.add_edge("1.2.2", "1.2.2.1") 319 graph.add_edge("1.2.2", "1.2.2.2") 320 graph.add_edge("1.2.2", "1.2.2.3") 321 322 result = list(graph.iterdfs("1")) 323 self.assertEqual(result, [ 324 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 325 '1.2.2.1', '1.2.1', '1.1', '1.1.2', '1.1.1' 326 ]) 327 result = list(graph.iterdfs("1", "1.2.1")) 328 self.assertEqual(result, [ 329 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 330 '1.2.2.1', '1.2.1' 331 ]) 332 333 result = graph.forw_dfs("1") 334 self.assertEqual(result, [ 335 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 336 '1.2.2.1', '1.2.1', '1.1', '1.1.2', '1.1.1' 337 ]) 338 result = graph.forw_dfs("1", "1.2.1") 339 self.assertEqual(result, [ 340 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 341 '1.2.2.1', '1.2.1' 342 ]) 343 344 graph = Graph() 345 graph.add_edge("1.1", "1") 346 graph.add_edge("1.2", "1") 347 graph.add_edge("1.3", "1") 348 graph.add_edge("1.1.1", "1.1") 349 graph.add_edge("1.1.2", "1.1") 350 graph.add_edge("1.2.1", "1.2") 351 graph.add_edge("1.2.2", "1.2") 352 graph.add_edge("1.2.2.1", "1.2.2") 353 graph.add_edge("1.2.2.2", "1.2.2") 354 graph.add_edge("1.2.2.3", "1.2.2") 355 356 result = list(graph.iterdfs("1", forward=False)) 357 self.assertEqual(result, [ 358 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 359 '1.2.2.1', '1.2.1', '1.1', '1.1.2', '1.1.1' 360 ]) 361 result = list(graph.iterdfs("1", "1.2.1", forward=False)) 362 self.assertEqual(result, [ 363 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 364 '1.2.2.1', '1.2.1' 365 ]) 366 result = graph.back_dfs("1") 367 self.assertEqual(result, [ 368 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 369 '1.2.2.1', '1.2.1', '1.1', '1.1.2', '1.1.1' 370 ]) 371 result = graph.back_dfs("1", "1.2.1") 372 self.assertEqual(result, [ 373 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 374 '1.2.2.1', '1.2.1' 375 ]) 376 377 378 # Introduce cyle: 379 graph.add_edge("1", "1.2") 380 result = list(graph.iterdfs("1", forward=False)) 381 self.assertEqual(result, [ 382 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 383 '1.2.2.1', '1.2.1', '1.1', '1.1.2', '1.1.1' 384 ]) 385 386 result = graph.back_dfs("1") 387 self.assertEqual(result, [ 388 '1', '1.3', '1.2', '1.2.2', '1.2.2.3', '1.2.2.2', 389 '1.2.2.1', '1.2.1', '1.1', '1.1.2', '1.1.1' 390 ]) 391 392 393 def test_iterdata(self): 394 graph = Graph() 395 graph.add_node("1", "I") 396 graph.add_node("1.1", "I.I") 397 graph.add_node("1.2", "I.II") 398 graph.add_node("1.3", "I.III") 399 graph.add_node("1.1.1", "I.I.I") 400 graph.add_node("1.1.2", "I.I.II") 401 graph.add_node("1.2.1", "I.II.I") 402 graph.add_node("1.2.2", "I.II.II") 403 graph.add_node("1.2.2.1", "I.II.II.I") 404 graph.add_node("1.2.2.2", "I.II.II.II") 405 graph.add_node("1.2.2.3", "I.II.II.III") 406 407 graph.add_edge("1", "1.1") 408 graph.add_edge("1", "1.2") 409 graph.add_edge("1", "1.3") 410 graph.add_edge("1.1", "1.1.1") 411 graph.add_edge("1.1", "1.1.2") 412 graph.add_edge("1.2", "1.2.1") 413 graph.add_edge("1.2", "1.2.2") 414 graph.add_edge("1.2.2", "1.2.2.1") 415 graph.add_edge("1.2.2", "1.2.2.2") 416 graph.add_edge("1.2.2", "1.2.2.3") 417 418 result = list(graph.iterdata("1", forward=True)) 419 self.assertEqual(result, [ 420 'I', 'I.III', 'I.II', 'I.II.II', 'I.II.II.III', 'I.II.II.II', 421 'I.II.II.I', 'I.II.I', 'I.I', 'I.I.II', 'I.I.I' 422 ]) 423 424 result = list(graph.iterdata("1", end="1.2.1", forward=True)) 425 self.assertEqual(result, [ 426 'I', 'I.III', 'I.II', 'I.II.II', 'I.II.II.III', 'I.II.II.II', 427 'I.II.II.I', 'I.II.I' 428 ]) 429 430 result = list(graph.iterdata("1", condition=lambda n: len(n) < 6, forward=True)) 431 self.assertEqual(result, [ 432 'I', 'I.III', 'I.II', 433 'I.I', 'I.I.I' 434 ]) 435 436 437 # And the revese option: 438 graph = Graph() 439 graph.add_node("1", "I") 440 graph.add_node("1.1", "I.I") 441 graph.add_node("1.2", "I.II") 442 graph.add_node("1.3", "I.III") 443 graph.add_node("1.1.1", "I.I.I") 444 graph.add_node("1.1.2", "I.I.II") 445 graph.add_node("1.2.1", "I.II.I") 446 graph.add_node("1.2.2", "I.II.II") 447 graph.add_node("1.2.2.1", "I.II.II.I") 448 graph.add_node("1.2.2.2", "I.II.II.II") 449 graph.add_node("1.2.2.3", "I.II.II.III") 450 451 graph.add_edge("1.1", "1") 452 graph.add_edge("1.2", "1") 453 graph.add_edge("1.3", "1") 454 graph.add_edge("1.1.1", "1.1") 455 graph.add_edge("1.1.2", "1.1") 456 graph.add_edge("1.2.1", "1.2") 457 graph.add_edge("1.2.2", "1.2") 458 graph.add_edge("1.2.2.1", "1.2.2") 459 graph.add_edge("1.2.2.2", "1.2.2") 460 graph.add_edge("1.2.2.3", "1.2.2") 461 462 result = list(graph.iterdata("1", forward=False)) 463 self.assertEqual(result, [ 464 'I', 'I.III', 'I.II', 'I.II.II', 'I.II.II.III', 'I.II.II.II', 465 'I.II.II.I', 'I.II.I', 'I.I', 'I.I.II', 'I.I.I' 466 ]) 467 468 result = list(graph.iterdata("1", end="1.2.1", forward=False)) 469 self.assertEqual(result, [ 470 'I', 'I.III', 'I.II', 'I.II.II', 'I.II.II.III', 'I.II.II.II', 471 'I.II.II.I', 'I.II.I' 472 ]) 473 474 result = list(graph.iterdata("1", condition=lambda n: len(n) < 6, forward=False)) 475 self.assertEqual(result, [ 476 'I', 'I.III', 'I.II', 477 'I.I', 'I.I.I' 478 ]) 479 480 def test_bfs(self): 481 graph = Graph() 482 graph.add_edge("1", "1.1") 483 graph.add_edge("1.1", "1.1.1") 484 graph.add_edge("1.1", "1.1.2") 485 graph.add_edge("1.1.2", "1.1.2.1") 486 graph.add_edge("1.1.2", "1.1.2.2") 487 graph.add_edge("1", "1.2") 488 graph.add_edge("1", "1.3") 489 graph.add_edge("1.2", "1.2.1") 490 491 self.assertEqual(graph.forw_bfs("1"), 492 ['1', '1.1', '1.2', '1.3', '1.1.1', '1.1.2', '1.2.1', '1.1.2.1', '1.1.2.2']) 493 self.assertEqual(graph.forw_bfs("1", "1.1.1"), 494 ['1', '1.1', '1.2', '1.3', '1.1.1']) 495 496 497 # And the "reverse" graph 498 graph = Graph() 499 graph.add_edge("1.1", "1") 500 graph.add_edge("1.1.1", "1.1") 501 graph.add_edge("1.1.2", "1.1") 502 graph.add_edge("1.1.2.1", "1.1.2") 503 graph.add_edge("1.1.2.2", "1.1.2") 504 graph.add_edge("1.2", "1") 505 graph.add_edge("1.3", "1") 506 graph.add_edge("1.2.1", "1.2") 507 508 self.assertEqual(graph.back_bfs("1"), 509 ['1', '1.1', '1.2', '1.3', '1.1.1', '1.1.2', '1.2.1', '1.1.2.1', '1.1.2.2']) 510 self.assertEqual(graph.back_bfs("1", "1.1.1"), 511 ['1', '1.1', '1.2', '1.3', '1.1.1']) 512 513 514 515 # check cycle handling 516 graph.add_edge("1", "1.2.1") 517 self.assertEqual(graph.back_bfs("1"), 518 ['1', '1.1', '1.2', '1.3', '1.1.1', '1.1.2', '1.2.1', '1.1.2.1', '1.1.2.2']) 519 520 521 def test_connected(self): 522 graph = Graph() 523 graph.add_node(1) 524 graph.add_node(2) 525 graph.add_node(3) 526 graph.add_node(4) 527 528 self.assertFalse(graph.connected()) 529 530 graph.add_edge(1, 2) 531 graph.add_edge(3, 4) 532 self.assertFalse(graph.connected()) 533 534 graph.add_edge(2, 3) 535 graph.add_edge(4, 1) 536 self.assertTrue(graph.connected()) 537 538 def test_edges_complex(self): 539 g = Graph() 540 g.add_edge(1, 2) 541 e = g.edge_by_node(1,2) 542 g.hide_edge(e) 543 g.hide_node(2) 544 self.assertRaises(GraphError, g.restore_edge, e) 545 546 g.restore_all_edges() 547 self.assertRaises(GraphError, g.edge_by_id, e) 548 549 def test_clust_coef(self): 550 g = Graph() 551 g.add_edge(1, 2) 552 g.add_edge(1, 3) 553 g.add_edge(1, 4) 554 self.assertEqual(g.clust_coef(1), 0) 555 556 g.add_edge(2, 5) 557 g.add_edge(3, 5) 558 g.add_edge(4, 5) 559 self.assertEqual(g.clust_coef(1), 0) 560 561 g.add_edge(2, 3) 562 self.assertEqual(g.clust_coef(1), 1./6) 563 g.add_edge(2, 4) 564 self.assertEqual(g.clust_coef(1), 2./6) 565 g.add_edge(4, 2) 566 self.assertEqual(g.clust_coef(1), 3./6) 567 568 g.add_edge(2, 3) 569 g.add_edge(2, 4) 570 g.add_edge(3, 4) 571 g.add_edge(3, 2) 572 g.add_edge(4, 2) 573 g.add_edge(4, 3) 574 self.assertEqual(g.clust_coef(1), 1) 575 576 577 def test_get_hops(self): 578 graph = Graph() 579 graph.add_edge(1, 2) 580 graph.add_edge(1, 3) 581 graph.add_edge(2, 4) 582 graph.add_edge(4, 5) 583 graph.add_edge(5, 7) 584 graph.add_edge(7, 8) 585 586 self.assertEqual(graph.get_hops(1), 587 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)]) 588 589 self.assertEqual(graph.get_hops(1, 5), 590 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3)]) 591 592 graph.add_edge(5, 1) 593 graph.add_edge(7, 1) 594 graph.add_edge(7, 4) 595 596 self.assertEqual(graph.get_hops(1), 597 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)]) 598 599 # And the reverse graph 600 graph = Graph() 601 graph.add_edge(2, 1) 602 graph.add_edge(3, 1) 603 graph.add_edge(4, 2) 604 graph.add_edge(5, 4) 605 graph.add_edge(7, 5) 606 graph.add_edge(8, 7) 607 608 self.assertEqual(graph.get_hops(1, forward=False), 609 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)]) 610 611 self.assertEqual(graph.get_hops(1, 5, forward=False), 612 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3)]) 613 614 graph.add_edge(1, 5) 615 graph.add_edge(1, 7) 616 graph.add_edge(4, 7) 617 618 self.assertEqual(graph.get_hops(1, forward=False), 619 [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)]) 620 621 622 def test_constructor(self): 623 graph = Graph(iter([ 624 (1, 2), 625 (2, 3, 'a'), 626 (1, 3), 627 (3, 4), 628 ])) 629 self.assertEqual(graph.number_of_nodes(), 4) 630 self.assertEqual(graph.number_of_edges(), 4) 631 try: 632 graph.edge_by_node(1,2) 633 graph.edge_by_node(2,3) 634 graph.edge_by_node(1,3) 635 graph.edge_by_node(3,4) 636 except GraphError: 637 self.fail("Incorrect graph") 638 639 self.assertEqual(graph.edge_data(graph.edge_by_node(2, 3)), 'a') 640 641 self.assertRaises(GraphError, Graph, [(1,2,3,4)]) 642 643if __name__ == "__main__": # pragma: no cover 644 unittest.main() 645