DetectNegativeCycleTest.php 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  1. <?php
  2. use Fhaculty\Graph\Graph;
  3. use Graphp\Algorithms\DetectNegativeCycle;
  4. class DetectNegativeCycleTest extends TestCase
  5. {
  6. public function testNullGraph()
  7. {
  8. $graph = new Graph();
  9. $alg = new DetectNegativeCycle($graph);
  10. $this->assertFalse($alg->hasCycleNegative());
  11. return $alg;
  12. }
  13. /**
  14. *
  15. * @param DetectNegativeCycle $alg
  16. * @depends testNullGraph
  17. * @expectedException UnderflowException
  18. */
  19. public function testNullGraphHasNoCycle(DetectNegativeCycle $alg)
  20. {
  21. $alg->getCycleNegative();
  22. }
  23. /**
  24. *
  25. * @param DetectNegativeCycle $alg
  26. * @depends testNullGraph
  27. * @expectedException UnderflowException
  28. */
  29. public function testNullGraphHasNoCycleGraph(DetectNegativeCycle $alg)
  30. {
  31. $alg->createGraph();
  32. }
  33. public function testNegativeLoop()
  34. {
  35. // 1 --[-1]--> 1
  36. $graph = new Graph();
  37. $v1 = $graph->createVertex(1);
  38. $e1 = $v1->createEdgeTo($v1)->setWeight(-1);
  39. $alg = new DetectNegativeCycle($graph);
  40. $this->assertTrue($alg->hasCycleNegative());
  41. $cycle = $alg->getCycleNegative();
  42. $this->assertCount(1, $cycle->getEdges());
  43. $this->assertCount(2, $cycle->getVertices());
  44. $this->assertEquals($e1, $cycle->getEdges()->getEdgeFirst());
  45. $this->assertEquals($v1, $cycle->getVertices()->getVertexFirst());
  46. }
  47. public function testNegativeCycle()
  48. {
  49. // 1 --[-1]--> 2
  50. // ^ |
  51. // \---[-2]----/
  52. $graph = new Graph();
  53. $v1 = $graph->createVertex(1);
  54. $v2 = $graph->createVertex(2);
  55. $e1 = $v1->createEdgeTo($v2)->setWeight(-1);
  56. $e2 = $v2->createEdgeTo($v1)->setWeight(-2);
  57. $alg = new DetectNegativeCycle($graph);
  58. $this->assertTrue($alg->hasCycleNegative());
  59. $cycle = $alg->getCycleNegative();
  60. $this->assertCount(2, $cycle->getEdges());
  61. $this->assertCount(3, $cycle->getVertices());
  62. }
  63. public function testNegativeUndirectedIsNegativeCycle()
  64. {
  65. // 1 --[-1]-- 2
  66. $graph = new Graph();
  67. $v1 = $graph->createVertex(1);
  68. $v2 = $graph->createVertex(2);
  69. $e1 = $v1->createEdge($v2)->setWeight(-1);
  70. $alg = new DetectNegativeCycle($graph);
  71. $this->assertTrue($alg->hasCycleNegative());
  72. $cycle = $alg->getCycleNegative();
  73. $this->assertCount(2, $cycle->getEdges());
  74. $this->assertCount(3, $cycle->getVertices());
  75. }
  76. public function testNegativeCycleSubgraph()
  77. {
  78. // 1 --[1]--> 2 --[1]--> 3 --[1]--> 4
  79. // ^ |
  80. // \---[-2]---/
  81. $graph = new Graph();
  82. $v1 = $graph->createVertex(1);
  83. $v2 = $graph->createVertex(2);
  84. $v3 = $graph->createVertex(3);
  85. $v4 = $graph->createVertex(4);
  86. $e1 = $v1->createEdgeTo($v2)->setWeight(1);
  87. $e2 = $v2->createEdgeTo($v3)->setWeight(1);
  88. $e3 = $v3->createEdgeTo($v4)->setWeight(1);
  89. $e4 = $v4->createEdgeTo($v3)->setWeight(-2);
  90. $alg = new DetectNegativeCycle($graph);
  91. $this->assertTrue($alg->hasCycleNegative());
  92. $cycle = $alg->getCycleNegative();
  93. $this->assertCount(2, $cycle->getEdges());
  94. $this->assertCount(3, $cycle->getVertices());
  95. $this->assertTrue($cycle->getVertices()->hasVertexId(3));
  96. $this->assertTrue($cycle->getVertices()->hasVertexId(4));
  97. }
  98. public function testNegativeComponents()
  99. {
  100. // 1 -- 2 3 --[-1]--> 4
  101. // ^ |
  102. // \---[-2]----/
  103. $graph = new Graph();
  104. $v1 = $graph->createVertex(1);
  105. $v2 = $graph->createVertex(2);
  106. $v3 = $graph->createVertex(3);
  107. $v4 = $graph->createVertex(4);
  108. $e1 = $v1->createEdge($v2);
  109. $e2 = $v3->createEdgeTo($v4)->setWeight(-1);
  110. $e3 = $v4->createEdgeTo($v3)->setWeight(-2);
  111. $alg = new DetectNegativeCycle($graph);
  112. $this->assertTrue($alg->hasCycleNegative());
  113. $cycle = $alg->getCycleNegative();
  114. $this->assertCount(2, $cycle->getEdges());
  115. $this->assertCount(3, $cycle->getVertices());
  116. $this->assertTrue($cycle->getVertices()->hasVertexId(3));
  117. $this->assertTrue($cycle->getVertices()->hasVertexId(4));
  118. }
  119. }