123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169 |
- <?php
- use Fhaculty\Graph\Graph;
- use Fhaculty\Graph\Vertex;
- use Fhaculty\Graph\Loader\CompleteGraph as LoaderCompleteGraph;
- use Graphp\Algorithms\MinimumSpanningTree\Base as MstBase;
- abstract class BaseMstTest extends TestCase
- {
- /**
- * @param Vertex $vertex
- * @return MstBase
- */
- abstract protected function createAlg(Vertex $vertex);
- public function testIsolatedVertex()
- {
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $alg = $this->createAlg($v1);
- $this->assertCount(0, $alg->getEdges());
- $this->assertEquals(0, $alg->getWeight());
- $graphMst = $alg->createGraph();
- $this->assertGraphEquals($graph, $graphMst);
- }
- public function testSingleEdge()
- {
- // 1 --[3]-- 2
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v1->createEdge($v2)->setWeight(3);
- $alg = $this->createAlg($v1);
- $this->assertCount(1, $alg->getEdges());
- $this->assertEquals(3, $alg->getWeight());
- $this->assertGraphEquals($graph, $alg->createGraph());
- }
- public function testSimpleGraph()
- {
- // 1 --[6]-- 2 --[9]-- 3 --[7]-- 4 --[8]-- 5
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v3 = $graph->createVertex(3);
- $v4 = $graph->createVertex(4);
- $v5 = $graph->createVertex(5);
- $v1->createEdge($v2)->setWeight(6);
- $v2->createEdge($v3)->setWeight(9);
- $v3->createEdge($v4)->setWeight(7);
- $v4->createEdge($v5)->setWeight(8);
- $alg = $this->createAlg($v1);
- $graphMst = $alg->createGraph();
- $this->assertGraphEquals($graph, $graphMst);
- }
- public function testFindingCheapestEdge()
- {
- // /--[4]--\
- // / \
- // 1 ---[3]--- 2
- // \ /
- // \--[5]--/
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v1->createEdge($v2)->setWeight(4);
- $v1->createEdge($v2)->setWeight(3);
- $v1->createEdge($v2)->setWeight(5);
- $alg = $this->createAlg($v1);
- $edges = $alg->getEdges();
- $this->assertCount(1, $edges);
- $this->assertEquals(3, $edges->getEdgeFirst()->getWeight());
- $this->assertEquals(3, $alg->getWeight());
- }
- public function testFindingCheapestTree()
- {
- // 1 --[4]-- 2 --[5]-- 3
- // \ /
- // \-------[6]-----/
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v3 = $graph->createVertex(3);
- $v1->createEdge($v2)->setWeight(4);
- $v2->createEdge($v3)->setWeight(5);
- $v3->createEdge($v1)->setWeight(6);
- // 1 --[4]-- 2 -- [5] -- 3
- $graphExpected = new Graph();
- $ve1 = $graphExpected->createVertex(1);
- $ve2 = $graphExpected->createVertex(2);
- $ve3 = $graphExpected->createVertex(3);
- $ve1->createEdge($ve2)->setWeight(4);
- $ve2->createEdge($ve3)->setWeight(5);
- $alg = $this->createAlg($v1);
- $this->assertCount(2, $alg->getEdges());
- $this->assertEquals(9, $alg->getWeight());
- $this->assertGraphEquals($graphExpected, $alg->createGraph());
- }
- public function testMixedGraphDirectionIsIgnored()
- {
- // 1 --[6]-> 2 --[7]-- 3 --[8]-- 4 <-[9]-- 5
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v3 = $graph->createVertex(3);
- $v4 = $graph->createVertex(4);
- $v5 = $graph->createVertex(5);
- $v1->createEdgeTo($v2)->setWeight(6);
- $v2->createEdge($v3)->setWeight(7);
- $v4->createEdge($v3)->setWeight(8);
- $v5->createEdgeTo($v4)->setWeight(9);
- $alg = $this->createAlg($v1);
- $this->assertCount(4, $alg->getEdges());
- $this->assertEquals(30, $alg->getWeight());
- $this->assertGraphEquals($graph, $alg->createGraph());
- }
- /**
- * @expectedException UnexpectedValueException
- */
- public function testMultipleComponentsFail()
- {
- // 1 --[1]-- 2, 3 --[1]-- 4
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v3 = $graph->createVertex(3);
- $v4 = $graph->createVertex(4);
- $v1->createEdge($v2)->setWeight(1);
- $v3->createEdge($v4)->setWeight(1);
- $alg = $this->createAlg($v1);
- $alg->getEdges();
- }
- /**
- * @expectedException UnexpectedValueException
- */
- public function testMultipleIsolatedVerticesFormMultipleComponentsFail()
- {
- // 1, 2
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $alg = $this->createAlg($v1);
- $alg->getEdges();
- }
- }
|