ResidualGraphTest.php 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. <?php
  2. use Fhaculty\Graph\Exception\UnexpectedValueException;
  3. use Fhaculty\Graph\Edge\Base as Edge;
  4. use Graphp\Algorithms\ResidualGraph;
  5. use Fhaculty\Graph\Graph;
  6. class ResidualGraphTest extends TestCase
  7. {
  8. public function testGraphEmpty()
  9. {
  10. $graph = new Graph();
  11. $alg = new ResidualGraph($graph);
  12. $residual = $alg->createGraph();
  13. $this->assertGraphEquals($graph, $residual);
  14. }
  15. /**
  16. * test an edge with capacity unused
  17. */
  18. public function testEdgeUnused()
  19. {
  20. $graph = new Graph();
  21. $graph->createVertex(0)->createEdgeTo($graph->createVertex(1))->setFlow(0)
  22. ->setCapacity(2)
  23. ->setWeight(3);
  24. $alg = new ResidualGraph($graph);
  25. $residual = $alg->createGraph();
  26. $this->assertGraphEquals($graph, $residual);
  27. }
  28. /**
  29. * test an edge with capacity completely used
  30. */
  31. public function testEdgeUsed()
  32. {
  33. $graph = new Graph();
  34. $graph->createVertex(0)->createEdgeTo($graph->createVertex(1))->setFlow(2)
  35. ->setCapacity(2)
  36. ->setWeight(3);
  37. $alg = new ResidualGraph($graph);
  38. $residual = $alg->createGraph();
  39. $expected = new Graph();
  40. $expected->createVertex(1)->createEdgeTo($expected->createVertex(0))->setFlow(0)
  41. ->setCapacity(2)
  42. ->setWeight(-3);
  43. $this->assertGraphEquals($expected, $residual);
  44. }
  45. /**
  46. * test an edge with capacity remaining
  47. */
  48. public function testEdgePartial()
  49. {
  50. $graph = new Graph();
  51. $graph->createVertex(0)->createEdgeTo($graph->createVertex(1))->setFlow(1)
  52. ->setCapacity(2)
  53. ->setWeight(3);
  54. $alg = new ResidualGraph($graph);
  55. $residual = $alg->createGraph();
  56. $expected = new Graph();
  57. $expected->createVertex(0);
  58. $expected->createVertex(1);
  59. // remaining edge
  60. $expected->getVertex(0)->createEdgeTo($expected->getVertex(1))->setFlow(0)
  61. ->setCapacity(1)
  62. ->setWeight(3);
  63. // back edge
  64. $expected->getVertex(1)->createEdgeTo($expected->getVertex(0))->setFlow(0)
  65. ->setCapacity(1)
  66. ->setWeight(-3);
  67. $this->assertGraphEquals($expected, $residual);
  68. }
  69. /**
  70. * expect exception for undirected edges
  71. * @expectedException UnexpectedValueException
  72. */
  73. public function testInvalidUndirected()
  74. {
  75. $graph = new Graph();
  76. $graph->createVertex()->createEdge($graph->createVertex())->setFlow(1)
  77. ->setCapacity(2);
  78. $alg = new ResidualGraph($graph);
  79. $alg->createGraph();
  80. }
  81. /**
  82. * expect exception for edges with no flow
  83. * @expectedException UnexpectedValueException
  84. */
  85. public function testInvalidNoFlow()
  86. {
  87. $graph = new Graph();
  88. $graph->createVertex()->createEdgeTo($graph->createVertex())->setCapacity(1);
  89. $alg = new ResidualGraph($graph);
  90. $alg->createGraph();
  91. }
  92. /**
  93. * expect exception for edges with no capacity
  94. * @expectedException UnexpectedValueException
  95. */
  96. public function testInvalidNoCapacity()
  97. {
  98. $graph = new Graph();
  99. $graph->createVertex()->createEdgeTo($graph->createVertex())->setFlow(1);
  100. $alg = new ResidualGraph($graph);
  101. $alg->createGraph();
  102. }
  103. }