123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199 |
- <?php
- use Graphp\Algorithms\Tree\BaseDirected;
- use Fhaculty\Graph\Exception\UnderflowException;
- use Fhaculty\Graph\Exception\UnexpectedValueException;
- use Fhaculty\Graph\Graph;
- use Fhaculty\Graph\Set\Vertices;
- abstract class BaseDirectedTest extends TestCase
- {
- /**
- *
- * @param Graph $graph
- * @return BaseDirected
- */
- abstract protected function createTreeAlg(Graph $graph);
- /**
- * @return Graph
- */
- abstract protected function createGraphNonTree();
- /**
- * @return Graph
- */
- abstract protected function createGraphTree();
- /**
- * @return Graph
- */
- abstract protected function createGraphParallelEdge();
- public function testNullGraph()
- {
- $graph = new Graph();
- $tree = $this->createTreeAlg($graph);
- $this->assertFalse($tree->isTree());
- $this->assertTrue($tree->getVerticesLeaf()->isEmpty());
- $this->assertTrue($tree->getVerticesInternal()->isEmpty());
- return $tree;
- }
- /**
- * @param BaseDirected $tree
- * @depends testNullGraph
- * @expectedException UnderflowException
- */
- public function testEmptyGraphDoesNotHaveRootVertex(BaseDirected $tree)
- {
- $tree->getVertexRoot();
- }
- /**
- * @param BaseDirected $tree
- * @depends testNullGraph
- * @expectedException UnderflowException
- */
- public function testEmptyGraphDoesNotHaveDegree(BaseDirected $tree)
- {
- $tree->getDegree();
- }
- /**
- * @param BaseDirected $tree
- * @depends testNullGraph
- * @expectedException UnderflowException
- */
- public function testEmptyGraphDoesNotHaveHeight(BaseDirected $tree)
- {
- $tree->getHeight();
- }
- public function testGraphTree()
- {
- $graph = $this->createGraphTree();
- $root = $graph->getVertices()->getVertexFirst();
- $nonRoot = $graph->getVertices()->getMap();
- unset($nonRoot[$root->getId()]);
- $nonRoot = new Vertices($nonRoot);
- $c1 = $nonRoot->getVertexFirst();
- $tree = $this->createTreeAlg($graph);
- $this->assertTrue($tree->isTree());
- $this->assertSame($root, $tree->getVertexRoot());
- $this->assertSame($graph->getVertices()->getVector(), $tree->getVerticesSubtree($root)->getVector());
- $this->assertSame($nonRoot->getVector(), $tree->getVerticesChildren($root)->getVector());
- $this->assertSame($nonRoot->getVector(), $tree->getVerticesDescendant($root)->getVector());
- $this->assertSame($nonRoot->getVector(), $tree->getVerticesLeaf()->getVector());
- $this->assertSame(array(), $tree->getVerticesInternal()->getVector());
- $this->assertSame($root, $tree->getVertexParent($c1));
- $this->assertSame(array(), $tree->getVerticesChildren($c1)->getVector());
- $this->assertSame(array(), $tree->getVerticesDescendant($c1)->getVector());
- $this->assertSame(array($c1), $tree->getVerticesSubtree($c1)->getVector());
- $this->assertEquals(2, $tree->getDegree());
- $this->assertEquals(0, $tree->getDepthVertex($root));
- $this->assertEquals(1, $tree->getDepthVertex($c1));
- $this->assertEquals(1, $tree->getHeight());
- $this->assertEquals(1, $tree->getHeightVertex($root));
- $this->assertEquals(0, $tree->getHeightvertex($c1));
- return $tree;
- }
- /**
- *
- * @param BaseDirected $tree
- * @depends testGraphTree
- * @expectedException UnderflowException
- */
- public function testGraphTreeRootDoesNotHaveParent(BaseDirected $tree)
- {
- $root = $tree->getVertexRoot();
- $tree->getVertexParent($root);
- }
- public function testNonTree()
- {
- $graph = $this->createGraphNonTree();
- $tree = $this->createTreeAlg($graph);
- $this->assertFalse($tree->isTree());
- }
- /**
- * @expectedException UnexpectedValueException
- */
- public function testNonTreeVertexHasMoreThanOneParent()
- {
- $graph = $this->createGraphNonTree();
- $tree = $this->createTreeAlg($graph);
- $tree->getVertexParent($graph->getVertex('v3'));
- }
- public function testGraphWithParallelEdgeIsNotTree()
- {
- $graph = $this->createGraphParallelEdge();
- $tree = $this->createTreeAlg($graph);
- $this->assertFalse($tree->isTree());
- }
- public function testGraphWithLoopIsNotTree()
- {
- // v1 -> v1
- $graph = new Graph();
- $graph->createVertex('v1')->createEdgeTo($graph->getVertex('v1'));
- $tree = $this->createTreeAlg($graph);
- $this->assertFalse($tree->isTree());
- }
- /**
- * @expectedException UnexpectedValueException
- */
- public function testGraphWithLoopCanNotGetSubgraph()
- {
- // v1 -> v1
- $graph = new Graph();
- $graph->createVertex('v1')->createEdgeTo($graph->getVertex('v1'));
- $tree = $this->createTreeAlg($graph);
- $tree->getVerticesSubtree($graph->getVertex('v1'));
- }
- public function testGraphWithUndirectedEdgeIsNotTree()
- {
- // v1 -- v2
- $graph = new Graph();
- $graph->createVertex('v1')->createEdge($graph->createVertex('v2'));
- $tree = $this->createTreeAlg($graph);
- $this->assertFalse($tree->isTree());
- }
- public function testGraphWithMixedEdgesIsNotTree()
- {
- // v1 -> v2 -- v3 -> v4
- $graph = new Graph();
- $graph->createVertex('v1')->createEdgeTo($graph->createVertex('v2'));
- $graph->getVertex('v2')->createEdge($graph->createVertex('v3'));
- $graph->getVertex('v3')->createEdgeTo($graph->createVertex('v4'));
- $tree = $this->createTreeAlg($graph);
- $this->assertFalse($tree->isTree());
- }
- }
|