123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151 |
- <?php
- use Fhaculty\Graph\Graph;
- use Graphp\Algorithms\DetectNegativeCycle;
- class DetectNegativeCycleTest extends TestCase
- {
- public function testNullGraph()
- {
- $graph = new Graph();
- $alg = new DetectNegativeCycle($graph);
- $this->assertFalse($alg->hasCycleNegative());
- return $alg;
- }
- /**
- *
- * @param DetectNegativeCycle $alg
- * @depends testNullGraph
- * @expectedException UnderflowException
- */
- public function testNullGraphHasNoCycle(DetectNegativeCycle $alg)
- {
- $alg->getCycleNegative();
- }
- /**
- *
- * @param DetectNegativeCycle $alg
- * @depends testNullGraph
- * @expectedException UnderflowException
- */
- public function testNullGraphHasNoCycleGraph(DetectNegativeCycle $alg)
- {
- $alg->createGraph();
- }
- public function testNegativeLoop()
- {
- // 1 --[-1]--> 1
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $e1 = $v1->createEdgeTo($v1)->setWeight(-1);
- $alg = new DetectNegativeCycle($graph);
- $this->assertTrue($alg->hasCycleNegative());
- $cycle = $alg->getCycleNegative();
- $this->assertCount(1, $cycle->getEdges());
- $this->assertCount(2, $cycle->getVertices());
- $this->assertEquals($e1, $cycle->getEdges()->getEdgeFirst());
- $this->assertEquals($v1, $cycle->getVertices()->getVertexFirst());
- }
- public function testNegativeCycle()
- {
- // 1 --[-1]--> 2
- // ^ |
- // \---[-2]----/
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $e1 = $v1->createEdgeTo($v2)->setWeight(-1);
- $e2 = $v2->createEdgeTo($v1)->setWeight(-2);
- $alg = new DetectNegativeCycle($graph);
- $this->assertTrue($alg->hasCycleNegative());
- $cycle = $alg->getCycleNegative();
- $this->assertCount(2, $cycle->getEdges());
- $this->assertCount(3, $cycle->getVertices());
- }
- public function testNegativeUndirectedIsNegativeCycle()
- {
- // 1 --[-1]-- 2
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $e1 = $v1->createEdge($v2)->setWeight(-1);
- $alg = new DetectNegativeCycle($graph);
- $this->assertTrue($alg->hasCycleNegative());
- $cycle = $alg->getCycleNegative();
- $this->assertCount(2, $cycle->getEdges());
- $this->assertCount(3, $cycle->getVertices());
- }
- public function testNegativeCycleSubgraph()
- {
- // 1 --[1]--> 2 --[1]--> 3 --[1]--> 4
- // ^ |
- // \---[-2]---/
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v3 = $graph->createVertex(3);
- $v4 = $graph->createVertex(4);
- $e1 = $v1->createEdgeTo($v2)->setWeight(1);
- $e2 = $v2->createEdgeTo($v3)->setWeight(1);
- $e3 = $v3->createEdgeTo($v4)->setWeight(1);
- $e4 = $v4->createEdgeTo($v3)->setWeight(-2);
- $alg = new DetectNegativeCycle($graph);
- $this->assertTrue($alg->hasCycleNegative());
- $cycle = $alg->getCycleNegative();
- $this->assertCount(2, $cycle->getEdges());
- $this->assertCount(3, $cycle->getVertices());
- $this->assertTrue($cycle->getVertices()->hasVertexId(3));
- $this->assertTrue($cycle->getVertices()->hasVertexId(4));
- }
- public function testNegativeComponents()
- {
- // 1 -- 2 3 --[-1]--> 4
- // ^ |
- // \---[-2]----/
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v3 = $graph->createVertex(3);
- $v4 = $graph->createVertex(4);
- $e1 = $v1->createEdge($v2);
- $e2 = $v3->createEdgeTo($v4)->setWeight(-1);
- $e3 = $v4->createEdgeTo($v3)->setWeight(-2);
- $alg = new DetectNegativeCycle($graph);
- $this->assertTrue($alg->hasCycleNegative());
- $cycle = $alg->getCycleNegative();
- $this->assertCount(2, $cycle->getEdges());
- $this->assertCount(3, $cycle->getVertices());
- $this->assertTrue($cycle->getVertices()->hasVertexId(3));
- $this->assertTrue($cycle->getVertices()->hasVertexId(4));
- }
- }
|