BaseShortestPathTest.php 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169
  1. <?php
  2. use Fhaculty\Graph\Graph;
  3. use Fhaculty\Graph\Vertex;
  4. use Graphp\Algorithms\ShortestPath\Base as ShortestPathAlg;
  5. abstract class BaseShortestPathTest extends TestCase
  6. {
  7. /**
  8. *
  9. * @param Vertex $vertex
  10. * @return ShortestPathAlg
  11. */
  12. abstract protected function createAlg(Vertex $vertex);
  13. abstract public function testGraphParallelNegative();
  14. public function testGraphTrivial()
  15. {
  16. // 1
  17. $graph = new Graph();
  18. $v1 = $graph->createVertex(1);
  19. $alg = $this->createAlg($v1);
  20. $this->assertFalse($alg->hasVertex($v1));
  21. //$this->assertEquals(0, $alg->getDistance($v1));
  22. $this->assertEquals(array(), $alg->getDistanceMap());
  23. $this->assertEquals(array(), $alg->getEdges()->getVector());
  24. //$this->assertEquals(array(), $alg->getEdgesTo($v1));
  25. $this->assertEquals(array(), $alg->getVertices()->getVector());
  26. $this->assertEquals(array(), $alg->getVertices()->getIds());
  27. $clone = $alg->createGraph();
  28. $this->assertGraphEquals($graph,$clone);
  29. }
  30. public function testGraphSingleLoop()
  31. {
  32. // 1 -[4]> 1
  33. $graph = new Graph();
  34. $v1 = $graph->createVertex(1);
  35. $e1 = $v1->createEdgeTo($v1)->setWeight(4);
  36. $alg = $this->createAlg($v1);
  37. $this->assertEquals(array($e1), $alg->getEdges()->getVector());
  38. $expectedWeight = $this->getExpectedWeight(array($e1));
  39. $this->assertTrue($alg->hasVertex($v1));
  40. $this->assertEquals($expectedWeight, $alg->getDistance($v1));
  41. $this->assertEquals(array(1 => $expectedWeight), $alg->getDistanceMap());
  42. $this->assertEquals(array($e1), $alg->getEdgesTo($v1)->getVector());
  43. $this->assertEquals(array(1 => $v1), $alg->getVertices()->getMap());
  44. $this->assertEquals(array(1), $alg->getVertices()->getIds());
  45. }
  46. public function testGraphCycle()
  47. {
  48. // 1 -[4]-> 2 -[2]-> 1
  49. $graph = new Graph();
  50. $v1 = $graph->createVertex(1);
  51. $v2 = $graph->createVertex(2);
  52. $e1 = $v1->createEdgeTo($v2)->setWeight(4);
  53. $e2 = $v2->createEdgeTo($v1)->setWeight(2);
  54. $alg = $this->createAlg($v1);
  55. //$this->assertEquals(array($e2, $e1), $alg->getEdges());
  56. $expectedWeight = $this->getExpectedWeight(array($e1));
  57. $this->assertTrue($alg->hasVertex($v2));
  58. $this->assertEquals(array($e1), $alg->getEdgesTo($v2)->getVector());
  59. $this->assertEquals($expectedWeight, $alg->getDistance($v2));
  60. $expectedWeight = $this->getExpectedWeight(array($e1, $e2));
  61. $this->assertTrue($alg->hasVertex($v1));
  62. $this->assertEquals(array($e1, $e2), $alg->getEdgesTo($v1)->getVector());
  63. $this->assertEquals($expectedWeight, $alg->getDistance($v1));
  64. $walk = $alg->getWalkTo($v1);
  65. $this->assertEquals(2, count($walk->getEdges()));
  66. }
  67. /**
  68. * @expectedException OutOfBoundsException
  69. */
  70. public function testIsolatedVertexIsNotReachable()
  71. {
  72. // 1, 2
  73. $graph = new Graph();
  74. $v1 = $graph->createVertex(1);
  75. $v2 = $graph->createVertex(2);
  76. $alg = $this->createAlg($v1);
  77. $this->assertFalse($alg->hasVertex($v2));
  78. $alg->getEdgesTo($v2);
  79. }
  80. /**
  81. * @expectedException OutOfBoundsException
  82. */
  83. public function testSeparateGraphsAreNotReachable()
  84. {
  85. // 1
  86. $graph1 = new Graph();
  87. $vg1 = $graph1->createVertex(1);
  88. $graph2 = new Graph();
  89. $vg2 = $graph2->createVertex(1);
  90. $alg = $this->createAlg($vg1);
  91. $alg->getEdgesTo($vg2);
  92. }
  93. public function testGraphUnweighted()
  94. {
  95. // 1 -> 2
  96. $graph = new Graph();
  97. $v1 = $graph->createVertex(1);
  98. $v2 = $graph->createVertex(2);
  99. $e1 = $v1->createEdgeTo($v2);
  100. $alg = $this->createAlg($v1);
  101. $expectedWeight = $this->getExpectedWeight(array($e1));
  102. $this->assertEquals($expectedWeight, $alg->getDistance($v2));
  103. $this->assertEquals(array(2 => $expectedWeight), $alg->getDistanceMap());
  104. $this->assertEquals(array($e1), $alg->getEdges()->getVector());
  105. $this->assertEquals(array($e1), $alg->getEdgesTo($v2)->getVector());
  106. $this->assertEquals(array(2), $alg->getVertices()->getIds());
  107. }
  108. public function testGraphTwoComponents()
  109. {
  110. // 1 -[10]-> 2
  111. // 3 -[20]-> 4
  112. $graph = new Graph();
  113. $v1 = $graph->createVertex(1);
  114. $v2 = $graph->createVertex(2);
  115. $v3 = $graph->createVertex(3);
  116. $v4 = $graph->createVertex(4);
  117. $e1 = $v1->createEdgeTo($v2)->setWeight(10);
  118. $e2 = $v3->createEdgeTo($v4)->setWeight(20);
  119. $alg = $this->createAlg($v1);
  120. $expectedWeight = $this->getExpectedWeight(array($e1));
  121. $this->assertEquals($expectedWeight, $alg->getDistance($v2));
  122. $this->assertEquals(array(2 => $expectedWeight), $alg->getDistanceMap());
  123. $this->assertEquals(array($e1), $alg->getEdges()->getVector());
  124. // $this->assertEquals(array(), $alg->getEdgesTo($v1));
  125. $this->assertEquals(array($e1), $alg->getEdgesTo($v2)->getVector());
  126. $this->assertEquals(array(2 => $v2), $alg->getVertices()->getMap());
  127. $this->assertEquals(array(2), $alg->getVertices()->getIds());
  128. }
  129. protected function getExpectedWeight($edges)
  130. {
  131. $sum = 0;
  132. foreach ($edges as $edge) {
  133. $sum += $edge->getWeight();
  134. }
  135. return $sum;
  136. }
  137. }