FlowTest.php 2.6 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
  1. <?php
  2. use Graphp\Algorithms\Flow as AlgorithmFlow;
  3. use Fhaculty\Graph\Graph;
  4. class FlowaTest extends TestCase
  5. {
  6. public function testGraphEmpty()
  7. {
  8. $graph = new Graph();
  9. $alg = new AlgorithmFlow($graph);
  10. $this->assertFalse($alg->hasFlow());
  11. $this->assertEquals(0, $alg->getBalance());
  12. $this->assertTrue($alg->isBalancedFlow());
  13. return $graph;
  14. }
  15. public function testEdgeWithZeroFlowIsConsideredFlow()
  16. {
  17. // 1 -> 2
  18. $graph = new Graph();
  19. $graph->createVertex(1)->createEdgeTo($graph->createVertex(2))->setFlow(0);
  20. $alg = new AlgorithmFlow($graph);
  21. $this->assertTrue($alg->hasFlow());
  22. $this->assertEquals(0, $alg->getFlowVertex($graph->getVertex(1)));
  23. $this->assertEquals(0, $alg->getFlowVertex($graph->getVertex(2)));
  24. }
  25. /**
  26. *
  27. * @param Graph $graph
  28. * @depends testGraphEmpty
  29. */
  30. public function testGraphSimple(Graph $graph)
  31. {
  32. // 1 -> 2
  33. $graph->createVertex(1)->createEdgeTo($graph->createVertex(2));
  34. $alg = new AlgorithmFlow($graph);
  35. $this->assertFalse($alg->hasFlow());
  36. $this->assertEquals(0, $alg->getFlowVertex($graph->getVertex(1)));
  37. $this->assertEquals(0, $alg->getFlowVertex($graph->getVertex(2)));
  38. return $graph;
  39. }
  40. /**
  41. *
  42. * @param Graph $graph
  43. * @depends testGraphSimple
  44. */
  45. public function testGraphWithUnweightedEdges(Graph $graph)
  46. {
  47. // additional flow edge: 2 -> 3
  48. $graph->getVertex(2)->createEdgeTo($graph->createVertex(3))->setFlow(10);
  49. $alg = new AlgorithmFlow($graph);
  50. $this->assertTrue($alg->hasFlow());
  51. $this->assertEquals(10, $alg->getFlowVertex($graph->getVertex(2)));
  52. $this->assertEquals(-10, $alg->getFlowVertex($graph->getVertex(3)));
  53. }
  54. public function testGraphBalance()
  55. {
  56. // source(+100) -> sink(-10)
  57. $graph = new Graph();
  58. $graph->createVertex('source')->setBalance(100);
  59. $graph->createVertex('sink')->setBalance(-10);
  60. $alg = new AlgorithmFlow($graph);
  61. $this->assertEquals(90, $alg->getBalance());
  62. $this->assertFalse($alg->isBalancedFlow());
  63. }
  64. /**
  65. * @expectedException UnexpectedValueException
  66. */
  67. public function testVertexWithUndirectedEdgeHasInvalidFlow()
  68. {
  69. // 1 -- 2
  70. $graph = new Graph();
  71. $graph->createVertex(1)->createEdge($graph->createVertex(2))->setFlow(10);
  72. $alg = new AlgorithmFlow($graph);
  73. $alg->getFlowVertex($graph->getVertex(1));
  74. }
  75. }