BaseMstTest.php 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169
  1. <?php
  2. use Fhaculty\Graph\Graph;
  3. use Fhaculty\Graph\Vertex;
  4. use Fhaculty\Graph\Loader\CompleteGraph as LoaderCompleteGraph;
  5. use Graphp\Algorithms\MinimumSpanningTree\Base as MstBase;
  6. abstract class BaseMstTest extends TestCase
  7. {
  8. /**
  9. * @param Vertex $vertex
  10. * @return MstBase
  11. */
  12. abstract protected function createAlg(Vertex $vertex);
  13. public function testIsolatedVertex()
  14. {
  15. $graph = new Graph();
  16. $v1 = $graph->createVertex(1);
  17. $alg = $this->createAlg($v1);
  18. $this->assertCount(0, $alg->getEdges());
  19. $this->assertEquals(0, $alg->getWeight());
  20. $graphMst = $alg->createGraph();
  21. $this->assertGraphEquals($graph, $graphMst);
  22. }
  23. public function testSingleEdge()
  24. {
  25. // 1 --[3]-- 2
  26. $graph = new Graph();
  27. $v1 = $graph->createVertex(1);
  28. $v2 = $graph->createVertex(2);
  29. $v1->createEdge($v2)->setWeight(3);
  30. $alg = $this->createAlg($v1);
  31. $this->assertCount(1, $alg->getEdges());
  32. $this->assertEquals(3, $alg->getWeight());
  33. $this->assertGraphEquals($graph, $alg->createGraph());
  34. }
  35. public function testSimpleGraph()
  36. {
  37. // 1 --[6]-- 2 --[9]-- 3 --[7]-- 4 --[8]-- 5
  38. $graph = new Graph();
  39. $v1 = $graph->createVertex(1);
  40. $v2 = $graph->createVertex(2);
  41. $v3 = $graph->createVertex(3);
  42. $v4 = $graph->createVertex(4);
  43. $v5 = $graph->createVertex(5);
  44. $v1->createEdge($v2)->setWeight(6);
  45. $v2->createEdge($v3)->setWeight(9);
  46. $v3->createEdge($v4)->setWeight(7);
  47. $v4->createEdge($v5)->setWeight(8);
  48. $alg = $this->createAlg($v1);
  49. $graphMst = $alg->createGraph();
  50. $this->assertGraphEquals($graph, $graphMst);
  51. }
  52. public function testFindingCheapestEdge()
  53. {
  54. // /--[4]--\
  55. // / \
  56. // 1 ---[3]--- 2
  57. // \ /
  58. // \--[5]--/
  59. $graph = new Graph();
  60. $v1 = $graph->createVertex(1);
  61. $v2 = $graph->createVertex(2);
  62. $v1->createEdge($v2)->setWeight(4);
  63. $v1->createEdge($v2)->setWeight(3);
  64. $v1->createEdge($v2)->setWeight(5);
  65. $alg = $this->createAlg($v1);
  66. $edges = $alg->getEdges();
  67. $this->assertCount(1, $edges);
  68. $this->assertEquals(3, $edges->getEdgeFirst()->getWeight());
  69. $this->assertEquals(3, $alg->getWeight());
  70. }
  71. public function testFindingCheapestTree()
  72. {
  73. // 1 --[4]-- 2 --[5]-- 3
  74. // \ /
  75. // \-------[6]-----/
  76. $graph = new Graph();
  77. $v1 = $graph->createVertex(1);
  78. $v2 = $graph->createVertex(2);
  79. $v3 = $graph->createVertex(3);
  80. $v1->createEdge($v2)->setWeight(4);
  81. $v2->createEdge($v3)->setWeight(5);
  82. $v3->createEdge($v1)->setWeight(6);
  83. // 1 --[4]-- 2 -- [5] -- 3
  84. $graphExpected = new Graph();
  85. $ve1 = $graphExpected->createVertex(1);
  86. $ve2 = $graphExpected->createVertex(2);
  87. $ve3 = $graphExpected->createVertex(3);
  88. $ve1->createEdge($ve2)->setWeight(4);
  89. $ve2->createEdge($ve3)->setWeight(5);
  90. $alg = $this->createAlg($v1);
  91. $this->assertCount(2, $alg->getEdges());
  92. $this->assertEquals(9, $alg->getWeight());
  93. $this->assertGraphEquals($graphExpected, $alg->createGraph());
  94. }
  95. public function testMixedGraphDirectionIsIgnored()
  96. {
  97. // 1 --[6]-> 2 --[7]-- 3 --[8]-- 4 <-[9]-- 5
  98. $graph = new Graph();
  99. $v1 = $graph->createVertex(1);
  100. $v2 = $graph->createVertex(2);
  101. $v3 = $graph->createVertex(3);
  102. $v4 = $graph->createVertex(4);
  103. $v5 = $graph->createVertex(5);
  104. $v1->createEdgeTo($v2)->setWeight(6);
  105. $v2->createEdge($v3)->setWeight(7);
  106. $v4->createEdge($v3)->setWeight(8);
  107. $v5->createEdgeTo($v4)->setWeight(9);
  108. $alg = $this->createAlg($v1);
  109. $this->assertCount(4, $alg->getEdges());
  110. $this->assertEquals(30, $alg->getWeight());
  111. $this->assertGraphEquals($graph, $alg->createGraph());
  112. }
  113. /**
  114. * @expectedException UnexpectedValueException
  115. */
  116. public function testMultipleComponentsFail()
  117. {
  118. // 1 --[1]-- 2, 3 --[1]-- 4
  119. $graph = new Graph();
  120. $v1 = $graph->createVertex(1);
  121. $v2 = $graph->createVertex(2);
  122. $v3 = $graph->createVertex(3);
  123. $v4 = $graph->createVertex(4);
  124. $v1->createEdge($v2)->setWeight(1);
  125. $v3->createEdge($v4)->setWeight(1);
  126. $alg = $this->createAlg($v1);
  127. $alg->getEdges();
  128. }
  129. /**
  130. * @expectedException UnexpectedValueException
  131. */
  132. public function testMultipleIsolatedVerticesFormMultipleComponentsFail()
  133. {
  134. // 1, 2
  135. $graph = new Graph();
  136. $v1 = $graph->createVertex(1);
  137. $v2 = $graph->createVertex(2);
  138. $alg = $this->createAlg($v1);
  139. $alg->getEdges();
  140. }
  141. }