1from apgl.graph.DictGraph import DictGraph 2from apgl.util.Util import Util 3import unittest 4import numpy 5import logging 6import numpy.testing as nptst 7 8class DictGraphTest(unittest.TestCase): 9 def setUp(self): 10 self.graph = DictGraph() 11 self.graph.addEdge(0, 1, 1) 12 self.graph.addEdge(1, 3, 1) 13 self.graph.addEdge(0, 2, 2) 14 self.graph.addEdge(2, 3, 5) 15 self.graph.addEdge(0, 4, 1) 16 self.graph.addEdge(3, 4, 1) 17 self.graph.setVertex(5, None) 18 19 self.graph2 = DictGraph(False) 20 self.graph2.addEdge(0, 1, 1) 21 self.graph2.addEdge(1, 3, 1) 22 self.graph2.addEdge(0, 2, 2) 23 self.graph2.addEdge(2, 3, 5) 24 self.graph2.addEdge(0, 4, 1) 25 self.graph2.addEdge(3, 4, 1) 26 self.graph2.setVertex(5, 1) 27 28 def testInit(self): 29 dictGraph = DictGraph() 30 31 def testAddEdge(self): 32 dictGraph = DictGraph() 33 dictGraph.addEdge("A", "B", [1,2,3]) 34 dictGraph.addEdge("A", "C", "HelloThere") 35 dictGraph.addEdge(12, 8, [1,2,3, 12]) 36 37 self.assertEquals(dictGraph.getEdge("A", "B"), [1,2,3]) 38 self.assertEquals(dictGraph.getEdge("B", "A"), [1,2,3]) 39 self.assertEquals(dictGraph.getEdge("A", "C"), "HelloThere") 40 self.assertEquals(dictGraph.getEdge("C", "A"), "HelloThere") 41 self.assertEquals(dictGraph.getEdge(12, 8), [1,2,3, 12]) 42 self.assertEquals(dictGraph.getEdge(8, 12), [1,2,3, 12]) 43 44 dictGraph.addEdge(2, 8) 45 46 dictGraph = DictGraph(False) 47 dictGraph.addEdge("A", "B", [1,2,3]) 48 dictGraph.addEdge("A", "C", "HelloThere") 49 dictGraph.addEdge(12, 8, [1,2,3, 12]) 50 51 self.assertEquals(dictGraph.getEdge("A", "B"), [1,2,3]) 52 self.assertEquals(dictGraph.getEdge("B", "A"), None) 53 self.assertEquals(dictGraph.getEdge("A", "C"), "HelloThere") 54 self.assertEquals(dictGraph.getEdge("C", "A"), None) 55 self.assertEquals(dictGraph.getEdge(12, 8), [1,2,3, 12]) 56 self.assertEquals(dictGraph.getEdge(8, 12), None) 57 58 dictGraph.addEdge(2, 8) 59 60 #Test directed graphs 61 62 def testRemoveEdge(self): 63 dictGraph = DictGraph() 64 dictGraph.addEdge(1, 2, 12) 65 dictGraph.addEdge(1, 3, 18) 66 dictGraph.addEdge(3, 4, 1) 67 68 self.assertEquals(dictGraph.getEdge(1, 2), 12) 69 self.assertEquals(dictGraph.getEdge(1, 3), 18) 70 self.assertEquals(dictGraph.getEdge(3, 4), 1) 71 72 dictGraph.removeEdge(1, 3) 73 74 self.assertEquals(dictGraph.getEdge(1, 3), None) 75 self.assertEquals(dictGraph.getEdge(1, 2), 12) 76 self.assertEquals(dictGraph.getEdge(3, 4), 1) 77 78 #Some tests on directed graphs 79 dictGraph = DictGraph(False) 80 dictGraph.addEdge(1, 2, 12) 81 dictGraph.addEdge(2, 1, 12) 82 83 dictGraph.removeEdge(1, 2) 84 self.assertEquals(dictGraph.getEdge(1, 2), None) 85 self.assertEquals(dictGraph.getEdge(2, 1), 12) 86 87 def testIsUndirected(self): 88 dictGraph = DictGraph(True) 89 self.assertEquals(dictGraph.isUndirected(), True) 90 91 dictGraph = DictGraph(False) 92 self.assertEquals(dictGraph.isUndirected(), False) 93 94 def testGetNumEdges(self): 95 dictGraph = DictGraph(True) 96 self.assertEquals(dictGraph.getNumEdges(), 0) 97 98 dictGraph.addEdge(1, 2, 12) 99 dictGraph.addEdge(1, 3, 18) 100 dictGraph.addEdge(3, 4, 1) 101 self.assertEquals(dictGraph.getNumEdges(), 3) 102 103 dictGraph.addEdge(3, 4, 1) 104 self.assertEquals(dictGraph.getNumEdges(), 3) 105 106 dictGraph.addEdge(3, 5, 1) 107 self.assertEquals(dictGraph.getNumEdges(), 4) 108 109 dictGraph.addEdge(3, 3, 1) 110 self.assertEquals(dictGraph.getNumEdges(), 5) 111 112 #Identical tests with directed graphs 113 dictGraph = DictGraph(False) 114 self.assertEquals(dictGraph.getNumEdges(), 0) 115 116 dictGraph.addEdge(1, 2, 12) 117 dictGraph.addEdge(1, 3, 18) 118 dictGraph.addEdge(3, 4, 1) 119 self.assertEquals(dictGraph.getNumEdges(), 3) 120 121 dictGraph.addEdge(3, 4, 1) 122 self.assertEquals(dictGraph.getNumEdges(), 3) 123 124 dictGraph.addEdge(3, 5, 1) 125 self.assertEquals(dictGraph.getNumEdges(), 4) 126 127 dictGraph.addEdge(3, 3, 1) 128 self.assertEquals(dictGraph.getNumEdges(), 5) 129 130 def testGetEdge(self): 131 dictGraph = DictGraph(True) 132 dictGraph.addEdge(1, 2, 12) 133 134 self.assertEquals(dictGraph.getEdge(1, 2), 12) 135 self.assertEquals(dictGraph.getEdge(2, 1), 12) 136 self.assertEquals(dictGraph.getEdge(2, 2), None) 137 self.assertRaises(ValueError, dictGraph.getEdge, 5, 8) 138 139 dictGraph = DictGraph(False) 140 dictGraph.addEdge(1, 2, 12) 141 142 self.assertEquals(dictGraph.getEdge(1, 2), 12) 143 self.assertEquals(dictGraph.getEdge(2, 1), None) 144 145 def testGetNeighbours(self): 146 dictGraph = DictGraph(True) 147 dictGraph.addEdge(1, 2, 12) 148 dictGraph.addEdge(1, 3, 18) 149 dictGraph.addEdge(1, 4, 1) 150 dictGraph.addEdge(3, 4, 1) 151 dictGraph.addEdge(2, 2, 1) 152 dictGraph.setVertex(5, 12) 153 154 self.assertEquals(dictGraph.neighbours(1), [2, 3, 4]) 155 self.assertEquals(dictGraph.neighbours(3), [1, 4]) 156 self.assertEquals(dictGraph.neighbours(2), [1, 2]) 157 self.assertEquals(dictGraph.neighbours(5), []) 158 159 #Directed graphs 160 dictGraph = DictGraph(False) 161 dictGraph.addEdge(1, 2, 12) 162 dictGraph.addEdge(1, 3, 18) 163 dictGraph.addEdge(1, 4, 1) 164 dictGraph.addEdge(3, 4, 1) 165 dictGraph.addEdge(2, 2, 1) 166 dictGraph.setVertex(5, 12) 167 168 self.assertEquals(dictGraph.neighbours(1), [2,3,4]) 169 self.assertEquals(dictGraph.neighbours(3), [4]) 170 self.assertEquals(dictGraph.neighbours(2), [2]) 171 self.assertEquals(dictGraph.neighbours(5), []) 172 173 def testGetVertex(self): 174 dictGraph = DictGraph(True) 175 dictGraph.addEdge(1, 2, 12) 176 dictGraph.addEdge(1, 3, 18) 177 dictGraph.setVertex(5, 12) 178 179 self.assertEquals(dictGraph.getVertex(1), None) 180 self.assertEquals(dictGraph.getVertex(2), None) 181 self.assertEquals(dictGraph.getVertex(3), None) 182 self.assertEquals(dictGraph.getVertex(5), 12) 183 184 self.assertRaises(ValueError, dictGraph.getVertex, 4) 185 186 #Directed graphs 187 dictGraph = DictGraph(False) 188 dictGraph.addEdge(1, 2, 12) 189 dictGraph.addEdge(1, 3, 18) 190 dictGraph.setVertex(5, 12) 191 192 self.assertEquals(dictGraph.getVertex(1), None) 193 self.assertEquals(dictGraph.getVertex(2), None) 194 self.assertEquals(dictGraph.getVertex(3), None) 195 self.assertEquals(dictGraph.getVertex(5), 12) 196 197 self.assertRaises(ValueError, dictGraph.getVertex, 4) 198 199 def testAddVertex(self): 200 dictGraph = DictGraph(True) 201 dictGraph.addEdge(1, 2, 12) 202 dictGraph.addEdge(1, 3, 18) 203 dictGraph.setVertex(5, 12) 204 205 self.assertEquals(dictGraph.getVertex(5), 12) 206 207 dictGraph.setVertex(5, 22) 208 self.assertEquals(dictGraph.getVertex(5), 22) 209 210 dictGraph.addEdge(5, 11, 18) 211 self.assertEquals(dictGraph.getVertex(5), 22) 212 213 def testGetAllVertexIds(self): 214 dictGraph = DictGraph(True) 215 dictGraph.addEdge(1, 2, 12) 216 dictGraph.addEdge(1, 3, 18) 217 dictGraph.setVertex(5, 12) 218 219 self.assertEquals(dictGraph.getAllVertexIds(), [1, 2, 3, 5]) 220 221 def testGetAllEdges(self): 222 dictGraph = DictGraph(True) 223 dictGraph.setVertex(5, 12) 224 dictGraph.addEdge(1, 2, 12) 225 dictGraph.addEdge(1, 3, 18) 226 227 edges = dictGraph.getAllEdges() 228 229 self.assertEquals(len(edges), 2) 230 self.assertTrue((1,2) in edges) 231 self.assertTrue((1,3) in edges) 232 233 dictGraph = DictGraph(False) 234 dictGraph.setVertex(5, 12) 235 dictGraph.addEdge(1, 2, 12) 236 dictGraph.addEdge(2, 1, 12) 237 dictGraph.addEdge(1, 3, 18) 238 239 edges = dictGraph.getAllEdges() 240 241 self.assertEquals(len(edges), 3) 242 self.assertTrue((1,2) in edges) 243 self.assertTrue((2,1) in edges) 244 self.assertTrue((1,3) in edges) 245 246 def testDensity(self): 247 numVertices = 10 248 graph = DictGraph(True) 249 for i in range(numVertices): 250 graph.setVertex(i, 0) 251 252 graph.addEdge(0, 1) 253 self.assertEquals(graph.density(), float(1)/45) 254 255 graph.addEdge(0, 2) 256 self.assertEquals(graph.density(), float(2)/45) 257 258 graph = DictGraph(False) 259 for i in range(numVertices): 260 graph.setVertex(i, 0) 261 graph.addEdge(0, 1) 262 self.assertEquals(graph.density(), float(1)/90) 263 264 graph.addEdge(0, 2) 265 self.assertEquals(graph.density(), float(2)/90) 266 267 #Test a graph with 1 vertex 268 graph = DictGraph(True) 269 graph.setVertex(0, 12) 270 271 self.assertEquals(graph.density(), 0) 272 273 graph.addEdge(0, 0) 274 self.assertEquals(graph.density(), 1) 275 276 def testSetVertices(self): 277 graph = DictGraph() 278 279 vertexIndices = [1, 2, 3] 280 vertices = ["a", "b", "c"] 281 282 graph.setVertices(vertexIndices, vertices) 283 284 vertexIndices2 = graph.getAllVertexIds() 285 vertices2 = graph.getVertices(vertexIndices2) 286 287 self.assertEquals(vertexIndices, vertexIndices2) 288 self.assertEquals(vertices, vertices2) 289 290 def testGetWeightMatrix(self): 291 graph = DictGraph() 292 graph.addEdge("a", "b") 293 graph.addEdge("a", "c") 294 graph.addEdge("a", "d") 295 graph.addEdge("d", "e") 296 297 W = graph.getWeightMatrix() 298 keys = graph.getAllVertexIds() 299 300 for i in range(len(keys)): 301 for j in range(len(keys)): 302 if W[i, j] == 1: 303 self.assertEquals(graph.getEdge(keys[i], keys[j]), 1) 304 else: 305 self.assertEquals(graph.getEdge(keys[i], keys[j]), None) 306 307 #Try a directed graph 308 graph = DictGraph(False) 309 graph.addEdge("a", "b") 310 graph.addEdge("a", "c") 311 graph.addEdge("a", "d") 312 graph.addEdge("d", "e") 313 314 W = graph.getWeightMatrix() 315 316 for i in range(len(keys)): 317 for j in range(len(keys)): 318 if W[i, j] == 1: 319 self.assertEquals(graph.getEdge(keys[i], keys[j]), 1) 320 else: 321 self.assertEquals(graph.getEdge(keys[i], keys[j]), None) 322 323 def testGetSparseWeightMatrix(self): 324 graph = DictGraph() 325 graph.addEdge("a", "b") 326 graph.addEdge("a", "c") 327 graph.addEdge("a", "d") 328 graph.addEdge("d", "e") 329 330 W = graph.getSparseWeightMatrix() 331 keys = graph.getAllVertexIds() 332 333 for i in range(len(keys)): 334 for j in range(len(keys)): 335 if W[i, j] == 1: 336 self.assertEquals(graph.getEdge(keys[i], keys[j]), 1) 337 else: 338 self.assertEquals(graph.getEdge(keys[i], keys[j]), None) 339 340 #Try a directed graph 341 graph = DictGraph(False) 342 graph.addEdge("a", "b") 343 graph.addEdge("a", "c") 344 graph.addEdge("a", "d") 345 graph.addEdge("d", "e") 346 347 W = graph.getSparseWeightMatrix() 348 349 for i in range(len(keys)): 350 for j in range(len(keys)): 351 if W[i, j] == 1: 352 self.assertEquals(graph.getEdge(keys[i], keys[j]), 1) 353 else: 354 self.assertEquals(graph.getEdge(keys[i], keys[j]), None) 355 356 def testGetAllEdgeIndices(self): 357 graph = DictGraph() 358 graph.addEdge("a", "b") 359 graph.addEdge("a", "c") 360 graph.addEdge("a", "d") 361 graph.addEdge("d", "e") 362 363 edgeIndices = graph.getAllEdgeIndices() 364 keys = graph.getAllVertexIds() 365 366 self.assertEquals(edgeIndices.shape[0], graph.getNumEdges()) 367 for i in range(edgeIndices.shape[0]): 368 self.assertTrue(graph.getEdge(keys[int(edgeIndices[i, 0])], keys[edgeIndices[i, 1]]) == 1) 369 370 graph = DictGraph(False) 371 graph.addEdge("a", "b") 372 graph.addEdge("b", "a") 373 graph.addEdge("a", "c") 374 graph.addEdge("a", "d") 375 graph.addEdge("d", "e") 376 377 edgeIndices = graph.getAllEdgeIndices() 378 keys = graph.getAllVertexIds() 379 self.assertEquals(edgeIndices.shape[0], graph.getNumEdges()) 380 for i in range(edgeIndices.shape[0]): 381 self.assertTrue(graph.getEdge(keys[int(edgeIndices[i, 0])], keys[edgeIndices[i, 1]]) == 1) 382 383 def testGetItem(self): 384 graph = DictGraph() 385 graph.addEdge(1, 1, 0.1) 386 graph.addEdge(1, 3, 0.5) 387 graph.addEdge(2, 4, 1) 388 graph.addEdge(2, 3, 2) 389 graph.setVertex(0, "abc") 390 391 self.assertEquals(graph[1,1], 0.1) 392 self.assertEquals(graph[1,3], 0.5) 393 394 395 def testSetItem(self): 396 graph = DictGraph() 397 graph.addEdge(1, 1, 0.1) 398 graph.addEdge(1, 3, 0.5) 399 400 self.assertEquals(graph[1,3], 0.5) 401 graph[1, 3] = 2 402 self.assertEquals(graph[1,3], 2) 403 404 def testAddEdges(self): 405 graph = DictGraph() 406 407 edgeList = [(1, 2), (2, 1), (5, 2), (8, 8)] 408 409 graph.addEdges(edgeList) 410 self.assertEquals(graph.getNumEdges(), 3) 411 self.assertEquals(graph.getEdge(1, 2), 1) 412 self.assertEquals(graph.getEdge(5, 2), 1) 413 self.assertEquals(graph.getEdge(2, 1), 1) 414 self.assertEquals(graph.getEdge(8, 8), 1) 415 416 edgeValues = [1, 2, 3, 4] 417 graph.addEdges(edgeList, edgeValues) 418 self.assertEquals(graph.getEdge(1, 2), 2) 419 self.assertEquals(graph.getEdge(5, 2), 3) 420 self.assertEquals(graph.getEdge(2, 1), 2) 421 self.assertEquals(graph.getEdge(8, 8), 4) 422 423 #Now test directed graphs 424 graph = DictGraph(False) 425 graph.addEdges(edgeList) 426 self.assertEquals(graph.getNumEdges(), 4) 427 self.assertEquals(graph.getEdge(1, 2), 1) 428 self.assertEquals(graph.getEdge(5, 2), 1) 429 self.assertEquals(graph.getEdge(2, 1), 1) 430 self.assertEquals(graph.getEdge(8, 8), 1) 431 432 edgeValues = [1, 2, 3, 4] 433 graph.addEdges(edgeList, edgeValues) 434 self.assertEquals(graph.getEdge(1, 2), 1) 435 self.assertEquals(graph.getEdge(5, 2), 3) 436 self.assertEquals(graph.getEdge(2, 1), 2) 437 self.assertEquals(graph.getEdge(8, 8), 4) 438 439 440 def testSubgraph(self): 441 graph = DictGraph() 442 443 graph.addEdge(0, 1) 444 graph.addEdge(0, 2) 445 graph.addEdge(0, 3) 446 graph.addEdge(1, 2) 447 graph.addEdge(2, 3) 448 graph.setVertex(0, "abc") 449 graph.setVertex(3, "cde") 450 451 self.assertEquals(graph.getNumEdges(), 5) 452 453 subgraph = graph.subgraph([0, 1, 2]) 454 self.assertEquals(subgraph.getNumVertices(), 3) 455 self.assertEquals(subgraph.getNumEdges(), 3) 456 self.assertEquals(subgraph.isUndirected(), True) 457 self.assertEquals(subgraph.getEdge(0, 1), 1) 458 self.assertEquals(subgraph.getEdge(0, 2), 1) 459 self.assertEquals(subgraph.getEdge(1, 2), 1) 460 self.assertEquals(subgraph.getVertex(0), "abc") 461 462 #Check the original graph is fine 463 self.assertEquals(graph.getNumVertices(), 4) 464 self.assertEquals(graph.getNumEdges(), 5) 465 self.assertEquals(graph.getVertex(0), "abc") 466 self.assertEquals(graph.getVertex(3), "cde") 467 468 #Now a quick test for directed graphs 469 graph = DictGraph(False) 470 471 graph.addEdge(0, 1) 472 graph.addEdge(0, 2) 473 graph.addEdge(0, 3) 474 graph.addEdge(1, 2) 475 graph.addEdge(2, 3) 476 477 subgraph = graph.subgraph([0, 1, 2]) 478 self.assertEquals(subgraph.getNumEdges(), 3) 479 self.assertEquals(subgraph.isUndirected(), False) 480 self.assertEquals(subgraph.getEdge(0, 1), 1) 481 self.assertEquals(subgraph.getEdge(0, 2), 1) 482 self.assertEquals(subgraph.getEdge(1, 2), 1) 483 484 def testNeighbourOf(self): 485 graph = DictGraph(True) 486 487 graph.addEdge(0, 1) 488 graph.addEdge(0, 2) 489 graph.addEdge(0, 3) 490 graph.addEdge(1, 2) 491 graph.addEdge(2, 3) 492 493 for i in range(4): 494 self.assertEquals(graph.neighbours(i), graph.neighbourOf(i)) 495 496 #Now test directed graph 497 graph = DictGraph(False) 498 499 graph.addEdge(0, 1) 500 graph.addEdge(0, 2) 501 graph.addEdge(0, 3) 502 graph.addEdge(1, 2) 503 graph.addEdge(2, 3) 504 505 self.assertEquals(graph.neighbourOf(0), []) 506 self.assertEquals(graph.neighbourOf(1), [0]) 507 self.assertEquals(graph.neighbourOf(2), [0,1]) 508 self.assertEquals(graph.neighbourOf(3), [0, 2]) 509 510 511 def testOutDegreeSequence(self): 512 graph = DictGraph(True) 513 514 graph.addEdge(0, 1) 515 graph.addEdge(0, 2) 516 graph.addEdge(0, 3) 517 graph.addEdge(1, 2) 518 graph.addEdge(2, 3) 519 520 degSeq, vertices = graph.outDegreeSequence() 521 522 self.assertTrue((degSeq == numpy.array([ 3, 2, 3, 2.])).all()) 523 self.assertTrue(vertices == [0, 1, 2, 3]) 524 525 #Test results on a directed graph 526 graph = DictGraph(False) 527 graph.addEdge(0, 1) 528 graph.addEdge(0, 2) 529 graph.addEdge(0, 3) 530 graph.addEdge(1, 2) 531 graph.addEdge(2, 3) 532 533 degSeq, vertices = graph.outDegreeSequence() 534 self.assertTrue((degSeq == numpy.array([ 3, 1, 1, 0])).all()) 535 536 def testInDegreeSequence(self): 537 graph = DictGraph(True) 538 539 graph.addEdge(0, 1) 540 graph.addEdge(0, 2) 541 graph.addEdge(0, 3) 542 graph.addEdge(1, 2) 543 graph.addEdge(2, 3) 544 545 degSeq, vertices = graph.inDegreeSequence() 546 547 self.assertTrue((degSeq == numpy.array([ 3, 2, 3, 2.])).all()) 548 self.assertTrue(vertices == [0, 1, 2, 3]) 549 550 #Test results on a directed graph 551 graph = DictGraph(False) 552 graph.addEdge(0, 1) 553 graph.addEdge(0, 2) 554 graph.addEdge(0, 3) 555 graph.addEdge(1, 2) 556 graph.addEdge(2, 3) 557 558 degSeq, vertices = graph.inDegreeSequence() 559 self.assertTrue((degSeq == numpy.array([ 0, 1, 2, 2])).all()) 560 561 def testVertexExists(self): 562 graph = DictGraph(False) 563 graph.addEdge(0, 1) 564 graph.addEdge(0, 2) 565 graph.addEdge(0, 3) 566 graph.addEdge(1, 2) 567 graph.addEdge(2, 3) 568 569 self.assertTrue(graph.vertexExists(0)) 570 self.assertTrue(graph.vertexExists(1)) 571 self.assertTrue(graph.vertexExists(2)) 572 self.assertTrue(graph.vertexExists(3)) 573 self.assertFalse(graph.vertexExists(4)) 574 575 def testRemoveVertex(self): 576 graph = DictGraph() 577 graph.addEdge(0, 1) 578 graph.addEdge(0, 2) 579 graph.addEdge(0, 3) 580 graph.addEdge(1, 2) 581 graph.addEdge(2, 3) 582 graph.addEdge(3, 4) 583 584 graph.removeVertex(4) 585 self.assertFalse(graph.vertexExists(4)) 586 self.assertFalse(graph.edgeExists(3, 4)) 587 588 graph.removeVertex(3) 589 self.assertFalse(graph.vertexExists(3)) 590 self.assertFalse(graph.edgeExists(2, 3)) 591 self.assertFalse(graph.edgeExists(0, 3)) 592 593 graph.removeVertex(2) 594 self.assertFalse(graph.vertexExists(2)) 595 self.assertFalse(graph.edgeExists(1, 2)) 596 self.assertFalse(graph.edgeExists(0, 2)) 597 598 self.assertTrue(graph.getAllVertexIds() == [0, 1]) 599 self.assertTrue(graph.getAllEdges() == [(0, 1)]) 600 601 #Try directed graph 602 graph = DictGraph(False) 603 graph.addEdge(0, 1) 604 graph.addEdge(1, 0) 605 graph.addEdge(0, 3) 606 graph.addEdge(1, 2) 607 graph.addEdge(2, 3) 608 graph.addEdge(3, 4) 609 610 graph.removeVertex(0) 611 612 self.assertFalse(graph.vertexExists(0)) 613 self.assertFalse(graph.edgeExists(0, 1)) 614 self.assertFalse(graph.edgeExists(0, 3)) 615 self.assertFalse(graph.edgeExists(1, 0)) 616 617 graph.removeVertex(2) 618 self.assertFalse(graph.vertexExists(2)) 619 self.assertFalse(graph.edgeExists(1, 2)) 620 self.assertFalse(graph.edgeExists(2, 3)) 621 622 self.assertTrue(graph.getAllVertexIds() == [1, 3, 4]) 623 self.assertTrue(graph.getAllEdges() == [(3, 4)]) 624 625 def testToSparseGraph(self): 626 graph = DictGraph() 627 graph.addEdge(0, 1) 628 graph.addEdge(0, 2) 629 graph.addEdge(0, 3) 630 graph.addEdge(1, 2) 631 graph.addEdge(2, 3) 632 graph.addEdge(3, 4) 633 634 graph2 = graph.toSparseGraph() 635 636 self.assertEquals(graph2[0, 1], 1) 637 self.assertEquals(graph2[0, 2], 1) 638 self.assertEquals(graph2[0, 3], 1) 639 self.assertEquals(graph2[2, 1], 1) 640 self.assertEquals(graph2[2, 3], 1) 641 self.assertEquals(graph2[3, 4], 1) 642 643 def testDepthFirstSearch(self): 644 graph = DictGraph() 645 graph.addEdge(0, 1) 646 graph.addEdge(1, 2) 647 graph.addEdge(1, 3) 648 graph.addEdge(2, 6) 649 graph.addEdge(4, 5) 650 651 self.assertEquals(graph.depthFirstSearch(0), [0,1,2,6,3]) 652 self.assertEquals(graph.depthFirstSearch(1), [1,0,2,6,3]) 653 self.assertEquals(graph.depthFirstSearch(6), [6,2,1,0,3]) 654 self.assertEquals(graph.depthFirstSearch(4), [4, 5]) 655 self.assertEquals(graph.depthFirstSearch(5), [5, 4]) 656 657 def testBreadthFirstSearch(self): 658 graph = DictGraph() 659 graph.addEdge(0, 1) 660 graph.addEdge(0, 7) 661 graph.addEdge(7, 8) 662 graph.addEdge(7, 9) 663 graph.addEdge(1, 2) 664 graph.addEdge(1, 3) 665 graph.addEdge(2, 6) 666 graph.addEdge(4, 5) 667 668 self.assertEquals(graph.breadthFirstSearch(0), [0,1, 7,2,3,8,9,6]) 669 self.assertEquals(graph.breadthFirstSearch(1), [1,0,2,3,7,6,8,9]) 670 self.assertEquals(graph.breadthFirstSearch(6), [6, 2,1,0,3,7,8,9]) 671 self.assertEquals(graph.breadthFirstSearch(4), [4, 5]) 672 self.assertEquals(graph.breadthFirstSearch(5), [5, 4]) 673 self.assertEquals(graph.breadthFirstSearch(7), [7, 0, 8, 9, 1, 2, 3, 6]) 674 675 def testDegreeSequence(self): 676 graph = DictGraph() 677 graph.setVertex("a", 10) 678 graph["b", "c"] = 1 679 graph["b", "d"] = 1 680 graph["d", "e"] = 1 681 graph["e", "e"] = 1 682 683 degreeDict = {} 684 degreeDict2 = {"a": 0, "b": 2, "c": 1, "d": 2, "e": 3} 685 686 for i, id in enumerate(graph.getAllVertexIds()): 687 degreeDict[id] = graph.degreeSequence()[i] 688 689 self.assertEquals(degreeDict, degreeDict2) 690 691 def testGetNumDirEdges(self): 692 graph = DictGraph() 693 graph.addEdge(0, 1, 0.1) 694 graph.addEdge(1, 2, 0.1) 695 696 self.assertTrue(graph.getNumDirEdges() == 4) 697 graph.addEdge(1, 1) 698 self.assertTrue(graph.getNumDirEdges() == 5) 699 700 graph = DictGraph(False) 701 graph.addEdge(0, 1) 702 graph.addEdge(1, 2) 703 704 self.assertTrue(graph.getNumDirEdges() == 2) 705 graph.addEdge(1, 1) 706 self.assertTrue(graph.getNumDirEdges() == 3) 707 708 def testDijkstrasAlgorithm(self): 709 graph = DictGraph() 710 711 graph.addEdge(0, 1, 1) 712 graph.addEdge(1, 2, 1) 713 graph.addEdge(1, 3, 1) 714 graph.addEdge(2, 4, 1) 715 graph.setVertex(4, 1) 716 717 self.assertTrue((graph.dijkstrasAlgorithm(0) == numpy.array([0, 1, 2, 2, 3])).all()) 718 self.assertTrue((graph.dijkstrasAlgorithm(1) == numpy.array([1, 0, 1, 1, 2])).all()) 719 self.assertTrue((graph.dijkstrasAlgorithm(2) == numpy.array([2, 1, 0, 2, 1])).all()) 720 self.assertTrue((graph.dijkstrasAlgorithm(3) == numpy.array([2, 1, 2, 0, 3])).all()) 721 self.assertTrue((graph.dijkstrasAlgorithm(4) == numpy.array([3, 2, 1, 3, 0])).all()) 722 723 724 #Test a graph which has an isolated node 725 graph = DictGraph() 726 graph.setVertex(5, 1) 727 728 graph.addEdge(0, 1, 1) 729 graph.addEdge(1, 2, 1) 730 graph.addEdge(1, 3, 1) 731 732 self.assertTrue((graph.dijkstrasAlgorithm(0) == numpy.array([0, 1, 2, 2, numpy.inf])).all()) 733 734 #Test a graph in a ring 735 graph = DictGraph() 736 737 graph.addEdge(0, 1, 1) 738 graph.addEdge(1, 2, 1) 739 graph.addEdge(2, 3, 1) 740 graph.addEdge(3, 4, 1) 741 graph.addEdge(4, 0, 1) 742 743 self.assertTrue((graph.dijkstrasAlgorithm(0) == numpy.array([0, 1, 2, 2, 1])).all()) 744 745 #Try case in which vertex ids are not numbers 746 graph = DictGraph() 747 748 graph.addEdge("a", "b", 1) 749 graph.addEdge("b", "c", 1) 750 graph.addEdge("b", "d", 1) 751 graph.addEdge("c", "e", 1) 752 753 inds = Util.argsort(graph.getAllVertexIds()) 754 self.assertTrue((graph.dijkstrasAlgorithm("a")[inds] == numpy.array([0, 1, 2, 2, 3])).all()) 755 self.assertTrue((graph.dijkstrasAlgorithm("b")[inds] == numpy.array([1, 0, 1, 1, 2])).all()) 756 self.assertTrue((graph.dijkstrasAlgorithm("c")[inds] == numpy.array([2, 1, 0, 2, 1])).all()) 757 self.assertTrue((graph.dijkstrasAlgorithm("d")[inds] == numpy.array([2, 1, 2, 0, 3])).all()) 758 self.assertTrue((graph.dijkstrasAlgorithm("e")[inds] == numpy.array([3, 2, 1, 3, 0])).all()) 759 760 def testAdjacencyList(self): 761 graph = DictGraph() 762 graph.addEdge("a", "b", 1) 763 graph.addEdge("b", "c", 1) 764 graph.addEdge("b", "d", 1) 765 graph.addEdge("c", "e", 1) 766 graph.setVertex("f", 1) 767 768 neighbourIndices, neighbourWeights = graph.adjacencyList() 769 770 vertexIds = graph.getAllVertexIds() 771 772 for i in range(len(neighbourIndices)): 773 for k, j in enumerate(neighbourIndices[i]): 774 self.assertTrue(graph.edgeExists(vertexIds[i], vertexIds[j])) 775 self.assertEquals(graph[vertexIds[i], vertexIds[j]], neighbourWeights[i][k]) 776 777 def testFindAllDistances(self): 778 P = self.graph.findAllDistances() 779 780 P2 = numpy.zeros((self.graph.size, self.graph.size)) 781 P2[0, :] = numpy.array([0, 1, 2, 2, 1, numpy.inf]) 782 P2[1, :] = numpy.array([1, 0, 3, 1, 2, numpy.inf]) 783 P2[2, :] = numpy.array([2, 3, 0, 4, 3, numpy.inf]) 784 P2[3, :] = numpy.array([2, 1, 4, 0, 1, numpy.inf]) 785 P2[4, :] = numpy.array([1, 2, 3, 1, 0, numpy.inf]) 786 P2[5, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, numpy.inf, numpy.inf, 0]) 787 788 self.assertTrue((P == P2).all()) 789 790 #Now test the directed graph 791 P = self.graph2.findAllDistances() 792 793 P2 = numpy.zeros((self.graph.size, self.graph.size)) 794 P2[0, :] = numpy.array([0, 1, 2, 2, 1, numpy.inf]) 795 P2[1, :] = numpy.array([numpy.inf, 0, numpy.inf, 1, 2, numpy.inf]) 796 P2[2, :] = numpy.array([numpy.inf, numpy.inf, 0, 5, 6, numpy.inf]) 797 P2[3, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, 0, 1, numpy.inf]) 798 P2[4, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, numpy.inf, 0, numpy.inf]) 799 P2[5, :] = numpy.array([numpy.inf, numpy.inf, numpy.inf, numpy.inf, numpy.inf, 0]) 800 801 self.assertTrue((P == P2).all()) 802 803 def testToIGraph(self): 804 try: 805 import igraph 806 except ImportError as error: 807 logging.debug(error) 808 return 809 810 graph = DictGraph() 811 812 graph["a", "b"] = 1 813 graph["b", "c"] = 2 814 815 ig = graph.toIGraph() 816 817 self.assertEquals(len(ig.vs), 3) 818 self.assertEquals(ig[0, 2], 1) 819 self.assertEquals(ig[1, 2], 1) 820 821if __name__ == "__main__": 822 #import sys;sys.argv = ['', 'Test.testName'] 823 unittest.main() 824