EdmondsKarpTest.php 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169
  1. <?php
  2. use Fhaculty\Graph\Exception\UnexpectedValueException;
  3. use Fhaculty\Graph\Graph;
  4. use Graphp\Algorithms\MaxFlow\EdmondsKarp as AlgorithmMaxFlowEdmondsKarp;
  5. class EdmondsKarpTest extends PHPUnit_Framework_TestCase
  6. {
  7. public function testEdgeDirected()
  8. {
  9. // 0 -[0/10]-> 1
  10. $graph = new Graph();
  11. $v0 = $graph->createVertex(0);
  12. $v1 = $graph->createVertex(1);
  13. $v0->createEdgeTo($v1)->setCapacity(10);
  14. // 0 -[10/10]-> 1
  15. $alg = new AlgorithmMaxFlowEdmondsKarp($v0, $v1);
  16. $this->assertEquals(10, $alg->getFlowMax());
  17. }
  18. public function testEdgesMultiplePaths()
  19. {
  20. // 0 -[0/5]---------> 1
  21. // | ^
  22. // | |
  23. // \-[0/7]-> 2 -[0/9]-/
  24. $graph = new Graph();
  25. $v0 = $graph->createVertex(0);
  26. $v1 = $graph->createVertex(1);
  27. $v2 = $graph->createVertex(2);
  28. $v0->createEdgeTo($v1)->setCapacity(5);
  29. $v0->createEdgeTo($v2)->setCapacity(7);
  30. $v2->createEdgeTo($v1)->setCapacity(9);
  31. // 0 -[5/5]---------> 1
  32. // | ^
  33. // | |
  34. // \-[7/7]-> 2 -[7/9]-/
  35. $alg = new AlgorithmMaxFlowEdmondsKarp($v0, $v1);
  36. $this->assertEquals(12, $alg->getFlowMax());
  37. }
  38. public function testEdgesMultiplePathsTwo()
  39. {
  40. // 0 -[0/5]---------> 1-[0/10]-> 3
  41. // | ^ |
  42. // | | |
  43. // \-[0/7]-> 2 -[0/9]-/ |
  44. // ^ |
  45. // \---[0/2]-----------/
  46. $graph = new Graph();
  47. $v0 = $graph->createVertex(0);
  48. $v1 = $graph->createVertex(1);
  49. $v2 = $graph->createVertex(2);
  50. $v3 = $graph->createVertex(3);
  51. $v4 = $graph->createVertex(4);
  52. $v5 = $graph->createVertex(5);
  53. $v0->createEdgeTo($v1)->setCapacity(5);
  54. $v0->createEdgeTo($v2)->setCapacity(7);
  55. $v2->createEdgeTo($v1)->setCapacity(9);
  56. $v1->createEdgeTo($v3)->setCapacity(10);
  57. $v3->createEdgeTo($v2)->setCapacity(2);
  58. $alg = new AlgorithmMaxFlowEdmondsKarp($v0, $v3);
  59. $this->assertEquals(10, $alg->getFlowMax());
  60. $alg = new AlgorithmMaxFlowEdmondsKarp($v0, $v2);
  61. $this->assertEquals(9, $alg->getFlowMax());
  62. }
  63. public function testEdgesMultiplePathsTree()
  64. {
  65. $graph = new Graph();
  66. $v0 = $graph->createVertex(0);
  67. $v1 = $graph->createVertex(1);
  68. $v2 = $graph->createVertex(2);
  69. $v3 = $graph->createVertex(3);
  70. $v0->createEdgeTo($v1)->setCapacity(4);
  71. $v0->createEdgeTo($v2)->setCapacity(2);
  72. $v1->createEdgeTo($v2)->setCapacity(3);
  73. $v1->createEdgeTo($v3)->setCapacity(1);
  74. $v2->createEdgeTo($v3)->setCapacity(6);
  75. $alg = new AlgorithmMaxFlowEdmondsKarp($v0, $v3);
  76. $this->assertEquals(6, $alg->getFlowMax());
  77. }
  78. // public function testEdgesParallel(){
  79. // $graph = new Graph();
  80. // $v0 = $graph->createVertex(0);
  81. // $v1 = $graph->createVertex(1);
  82. // $v0->createEdgeTo($v1)->setCapacity(3.4);
  83. // $v0->createEdgeTo($v1)->setCapacity(6.6);
  84. // $alg = new AlgorithmMaxFlowEdmondsKarp($v0, $v1);
  85. // $this->assertEquals(10, $alg->getFlowMax());
  86. // }
  87. /**
  88. * @expectedException UnexpectedValueException
  89. */
  90. public function testEdgesUndirected()
  91. {
  92. // 0 -[0/7]- 1
  93. $graph = new Graph();
  94. $v0 = $graph->createVertex(0);
  95. $v1 = $graph->createVertex(1);
  96. $v1->createEdge($v0)->setCapacity(7);
  97. // 0 -[7/7]- 1
  98. $alg = new AlgorithmMaxFlowEdmondsKarp($v0, $v1);
  99. $this->assertEquals(7, $alg->getFlowMax());
  100. }
  101. /**
  102. * run algorithm with bigger graph and check result against known result (will take several seconds)
  103. */
  104. // public function testKnownResultBig(){
  105. // $graph = $this->readGraph('G_1_2.txt');
  106. // $alg = new AlgorithmMaxFlowEdmondsKarp($graph->getVertex(0), $graph->getVertex(4));
  107. // $this->assertEquals(0.735802, $alg->getFlowMax());
  108. // }
  109. /**
  110. * @expectedException InvalidArgumentException
  111. */
  112. public function testInvalidFlowToOtherGraph()
  113. {
  114. $graph1 = new Graph();
  115. $vg1 = $graph1->createVertex(1);
  116. $graph2 = new Graph();
  117. $vg2 = $graph2->createVertex(2);
  118. new AlgorithmMaxFlowEdmondsKarp($vg1, $vg2);
  119. }
  120. /**
  121. * @expectedException InvalidArgumentException
  122. */
  123. public function testInvalidFlowToSelf()
  124. {
  125. $graph = new Graph();
  126. $v1 = $graph->createVertex(1);
  127. new AlgorithmMaxFlowEdmondsKarp($v1, $v1);
  128. }
  129. }