BaseMcfTest.php 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203
  1. <?php
  2. use Graphp\Algorithms\MinimumCostFlow\Base;
  3. use Fhaculty\Graph\Graph;
  4. abstract class BaseMcfTest extends TestCase
  5. {
  6. /**
  7. *
  8. * @param Graph $graph
  9. * @return Base
  10. */
  11. abstract protected function createAlgorithm(Graph $graph);
  12. public function testNull()
  13. {
  14. $graph = new Graph();
  15. $alg = $this->createAlgorithm($graph);
  16. $this->assertEquals(0, $alg->getWeightFlow());
  17. }
  18. public function testSingleIntermediary()
  19. {
  20. $graph = new Graph();
  21. $v1 = $graph->createVertex(1);
  22. $alg = $this->createAlgorithm($graph);
  23. $this->assertEquals(0, $alg->getWeightFlow());
  24. }
  25. public function testSimpleEdge()
  26. {
  27. // 1(+2) -[0/2/2]-> 2(-2)
  28. $graph = new Graph();
  29. $v1 = $graph->createVertex(1)->setBalance(2);
  30. $v2 = $graph->createVertex(2)->setBalance(-2);
  31. $v1->createEdgeTo($v2)->setWeight(2)->setCapacity(2);
  32. $alg = $this->createAlgorithm($graph);
  33. $this->assertEquals(4, $alg->getWeightFlow()); // 2x2
  34. }
  35. public function testMultipleSinks()
  36. {
  37. // 1(+2) -[0/2/2]-> 2(-1)
  38. // -[0/4/-5]-> 3(-1)
  39. $graph = new Graph();
  40. $v1 = $graph->createVertex(1)->setBalance(2);
  41. $v2 = $graph->createVertex(2)->setBalance(-1);
  42. $v3 = $graph->createVertex(3)->setBalance(-1);
  43. $v1->createEdgeTo($v2)->setWeight(2)->setCapacity(2);
  44. $v1->createEdgeTo($v3)->setWeight(-5)->setCapacity(4);
  45. $alg = $this->createAlgorithm($graph);
  46. $this->assertEquals(-3, $alg->getWeightFlow()); // 1*2 + 1*-5
  47. }
  48. public function testIntermediaryVertices()
  49. {
  50. // 1(+2) -[0/1/4]-> 2 -[0/6/-2]-> 4(-2)
  51. // -[0/4/5]-> 3 -[0/6/8]->
  52. $graph = new Graph();
  53. $v1 = $graph->createVertex(1)->setBalance(2);
  54. $v2 = $graph->createVertex(2);
  55. $v3 = $graph->createVertex(3);
  56. $v4 = $graph->createVertex(4)->setBalance(-2);
  57. $v1->createEdgeTo($v2)->setWeight(4)->setCapacity(1);
  58. $v2->createEdgeTo($v4)->setWeight(-2)->setCapacity(6);
  59. $v1->createEdgeTo($v3)->setWeight(5)->setCapacity(4);
  60. $v3->createEdgeTo($v4)->setWeight(8)->setCapacity(6);
  61. $alg = $this->createAlgorithm($graph);
  62. $this->assertEquals(15, $alg->getWeightFlow()); // 1*4 + 1*-2 + 1*5 + 1*8
  63. }
  64. public function testEdgeCapacities()
  65. {
  66. // 1(+2) -[0/3/4]-> 2 -[0/4/5]-> 3 ->[0/6/-2]-> 4(-2)
  67. $graph = new Graph();
  68. $v1 = $graph->createVertex(1)->setBalance(2);
  69. $v2 = $graph->createVertex(2);
  70. $v3 = $graph->createVertex(3);
  71. $v4 = $graph->createVertex(4)->setBalance(-2);
  72. $v1->createEdgeTo($v2)->setWeight(4)->setCapacity(3);
  73. $v2->createEdgeTo($v3)->setWeight(5)->setCapacity(4);
  74. $v3->createEdgeTo($v4)->setWeight(-2)->setCapacity(6);
  75. $alg = $this->createAlgorithm($graph);
  76. $this->assertEquals(14, $alg->getWeightFlow()); // 2*4 + 2*5 + 2*-2
  77. }
  78. public function testEdgeFlows()
  79. {
  80. // 1(+4) ---[3/4/2]---> 2 ---[3/3/3]---> 4(-4)
  81. // | | ^
  82. // | [0/2/1] |
  83. // | ↓ |
  84. // \-------[1/2/2]---> 3 ---[1/5/1]-------/
  85. $graph = new Graph();
  86. $v1 = $graph->createVertex(1)->setBalance(4);
  87. $v2 = $graph->createVertex(2);
  88. $v3 = $graph->createVertex(3);
  89. $v4 = $graph->createVertex(4)->setBalance(-4);
  90. $v1->createEdgeTo($v2)->setFlow(3)->setCapacity(4)->setWeight(2);
  91. $v2->createEdgeTo($v4)->setFlow(3)->setCapacity(3)->setWeight(3);
  92. $v1->createEdgeTo($v3)->setFlow(1)->setCapacity(2)->setWeight(2);
  93. $v3->createEdgeTo($v4)->setFlow(1)->setCapacity(5)->setWeight(1);
  94. $v2->createEdgeTo($v3)->setFlow(0)->setCapacity(2)->setWeight(1);
  95. $alg = $this->createAlgorithm($graph);
  96. $this->assertEquals(14, $alg->getWeightFlow()); // 4*1 + 2*2 + 2*1 + 2*2
  97. }
  98. /**
  99. * @expectedException UnexpectedValueException
  100. */
  101. public function testEdgeCapacityInsufficientFails()
  102. {
  103. // 1(+2) -[0/1]-> 2(-2)
  104. $graph = new Graph();
  105. $v1 = $graph->createVertex(1)->setBalance(2);
  106. $v2 = $graph->createVertex(2)->setBalance(-2);
  107. $v1->createEdgeTo($v2)->setCapacity(1);
  108. $alg = $this->createAlgorithm($graph);
  109. $alg->getWeightFlow();
  110. }
  111. /**
  112. * @expectedException UnexpectedValueException
  113. */
  114. public function testEdgeCapacityUnsetFails()
  115. {
  116. // 1(+2) -> 2(-2)
  117. $graph = new Graph();
  118. $v1 = $graph->createVertex(1)->setBalance(2);
  119. $v2 = $graph->createVertex(2)->setBalance(-2);
  120. $v1->createEdgeTo($v2);
  121. $alg = $this->createAlgorithm($graph);
  122. $alg->getWeightFlow();
  123. }
  124. /**
  125. * @expectedException UnexpectedValueException
  126. */
  127. public function testIsolatedVerticesFail()
  128. {
  129. // 1(+2), 2(-2)
  130. $graph = new Graph();
  131. $v1 = $graph->createVertex(1)->setBalance(2);
  132. $v2 = $graph->createVertex(2)->setBalance(-2);
  133. $alg = $this->createAlgorithm($graph);
  134. $alg->getWeightFlow();
  135. }
  136. /**
  137. * @expectedException UnexpectedValueException
  138. */
  139. public function testUnbalancedFails()
  140. {
  141. // 1(+2) -> 2(-3)
  142. $graph = new Graph();
  143. $v1 = $graph->createVertex(1)->setBalance(2);
  144. $v2 = $graph->createVertex(2)->setBalance(-3);
  145. $v1->createEdgeTo($v2)->setCapacity(3);
  146. $alg = $this->createAlgorithm($graph);
  147. $alg->getWeightFlow();
  148. }
  149. /**
  150. * @expectedException UnexpectedValueException
  151. */
  152. public function testUndirectedFails()
  153. {
  154. // 1(+2) -- 2(-2)
  155. $graph = new Graph();
  156. $v1 = $graph->createVertex(1)->setBalance(2);
  157. $v2 = $graph->createVertex(2)->setBalance(-2);
  158. $v1->createEdge($v2)->setCapacity(2);
  159. $alg = $this->createAlgorithm($graph);
  160. $alg->getWeightFlow();
  161. }
  162. /**
  163. * @expectedException UnexpectedValueException
  164. */
  165. public function testUndirectedNegativeCycleFails()
  166. {
  167. // 1(+2) -[0/2/-1]- 2(-2)
  168. $graph = new Graph();
  169. $v1 = $graph->createVertex(1)->setBalance(2);
  170. $v2 = $graph->createVertex(2)->setBalance(-2);
  171. $v1->createEdge($v2)->setCapacity(2)->setWeight(-1);
  172. $alg = $this->createAlgorithm($graph);
  173. $alg->getWeightFlow();
  174. }
  175. }