BaseDirectedTest.php 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199
  1. <?php
  2. use Graphp\Algorithms\Tree\BaseDirected;
  3. use Fhaculty\Graph\Exception\UnderflowException;
  4. use Fhaculty\Graph\Exception\UnexpectedValueException;
  5. use Fhaculty\Graph\Graph;
  6. use Fhaculty\Graph\Set\Vertices;
  7. abstract class BaseDirectedTest extends TestCase
  8. {
  9. /**
  10. *
  11. * @param Graph $graph
  12. * @return BaseDirected
  13. */
  14. abstract protected function createTreeAlg(Graph $graph);
  15. /**
  16. * @return Graph
  17. */
  18. abstract protected function createGraphNonTree();
  19. /**
  20. * @return Graph
  21. */
  22. abstract protected function createGraphTree();
  23. /**
  24. * @return Graph
  25. */
  26. abstract protected function createGraphParallelEdge();
  27. public function testNullGraph()
  28. {
  29. $graph = new Graph();
  30. $tree = $this->createTreeAlg($graph);
  31. $this->assertFalse($tree->isTree());
  32. $this->assertTrue($tree->getVerticesLeaf()->isEmpty());
  33. $this->assertTrue($tree->getVerticesInternal()->isEmpty());
  34. return $tree;
  35. }
  36. /**
  37. * @param BaseDirected $tree
  38. * @depends testNullGraph
  39. * @expectedException UnderflowException
  40. */
  41. public function testEmptyGraphDoesNotHaveRootVertex(BaseDirected $tree)
  42. {
  43. $tree->getVertexRoot();
  44. }
  45. /**
  46. * @param BaseDirected $tree
  47. * @depends testNullGraph
  48. * @expectedException UnderflowException
  49. */
  50. public function testEmptyGraphDoesNotHaveDegree(BaseDirected $tree)
  51. {
  52. $tree->getDegree();
  53. }
  54. /**
  55. * @param BaseDirected $tree
  56. * @depends testNullGraph
  57. * @expectedException UnderflowException
  58. */
  59. public function testEmptyGraphDoesNotHaveHeight(BaseDirected $tree)
  60. {
  61. $tree->getHeight();
  62. }
  63. public function testGraphTree()
  64. {
  65. $graph = $this->createGraphTree();
  66. $root = $graph->getVertices()->getVertexFirst();
  67. $nonRoot = $graph->getVertices()->getMap();
  68. unset($nonRoot[$root->getId()]);
  69. $nonRoot = new Vertices($nonRoot);
  70. $c1 = $nonRoot->getVertexFirst();
  71. $tree = $this->createTreeAlg($graph);
  72. $this->assertTrue($tree->isTree());
  73. $this->assertSame($root, $tree->getVertexRoot());
  74. $this->assertSame($graph->getVertices()->getVector(), $tree->getVerticesSubtree($root)->getVector());
  75. $this->assertSame($nonRoot->getVector(), $tree->getVerticesChildren($root)->getVector());
  76. $this->assertSame($nonRoot->getVector(), $tree->getVerticesDescendant($root)->getVector());
  77. $this->assertSame($nonRoot->getVector(), $tree->getVerticesLeaf()->getVector());
  78. $this->assertSame(array(), $tree->getVerticesInternal()->getVector());
  79. $this->assertSame($root, $tree->getVertexParent($c1));
  80. $this->assertSame(array(), $tree->getVerticesChildren($c1)->getVector());
  81. $this->assertSame(array(), $tree->getVerticesDescendant($c1)->getVector());
  82. $this->assertSame(array($c1), $tree->getVerticesSubtree($c1)->getVector());
  83. $this->assertEquals(2, $tree->getDegree());
  84. $this->assertEquals(0, $tree->getDepthVertex($root));
  85. $this->assertEquals(1, $tree->getDepthVertex($c1));
  86. $this->assertEquals(1, $tree->getHeight());
  87. $this->assertEquals(1, $tree->getHeightVertex($root));
  88. $this->assertEquals(0, $tree->getHeightvertex($c1));
  89. return $tree;
  90. }
  91. /**
  92. *
  93. * @param BaseDirected $tree
  94. * @depends testGraphTree
  95. * @expectedException UnderflowException
  96. */
  97. public function testGraphTreeRootDoesNotHaveParent(BaseDirected $tree)
  98. {
  99. $root = $tree->getVertexRoot();
  100. $tree->getVertexParent($root);
  101. }
  102. public function testNonTree()
  103. {
  104. $graph = $this->createGraphNonTree();
  105. $tree = $this->createTreeAlg($graph);
  106. $this->assertFalse($tree->isTree());
  107. }
  108. /**
  109. * @expectedException UnexpectedValueException
  110. */
  111. public function testNonTreeVertexHasMoreThanOneParent()
  112. {
  113. $graph = $this->createGraphNonTree();
  114. $tree = $this->createTreeAlg($graph);
  115. $tree->getVertexParent($graph->getVertex('v3'));
  116. }
  117. public function testGraphWithParallelEdgeIsNotTree()
  118. {
  119. $graph = $this->createGraphParallelEdge();
  120. $tree = $this->createTreeAlg($graph);
  121. $this->assertFalse($tree->isTree());
  122. }
  123. public function testGraphWithLoopIsNotTree()
  124. {
  125. // v1 -> v1
  126. $graph = new Graph();
  127. $graph->createVertex('v1')->createEdgeTo($graph->getVertex('v1'));
  128. $tree = $this->createTreeAlg($graph);
  129. $this->assertFalse($tree->isTree());
  130. }
  131. /**
  132. * @expectedException UnexpectedValueException
  133. */
  134. public function testGraphWithLoopCanNotGetSubgraph()
  135. {
  136. // v1 -> v1
  137. $graph = new Graph();
  138. $graph->createVertex('v1')->createEdgeTo($graph->getVertex('v1'));
  139. $tree = $this->createTreeAlg($graph);
  140. $tree->getVerticesSubtree($graph->getVertex('v1'));
  141. }
  142. public function testGraphWithUndirectedEdgeIsNotTree()
  143. {
  144. // v1 -- v2
  145. $graph = new Graph();
  146. $graph->createVertex('v1')->createEdge($graph->createVertex('v2'));
  147. $tree = $this->createTreeAlg($graph);
  148. $this->assertFalse($tree->isTree());
  149. }
  150. public function testGraphWithMixedEdgesIsNotTree()
  151. {
  152. // v1 -> v2 -- v3 -> v4
  153. $graph = new Graph();
  154. $graph->createVertex('v1')->createEdgeTo($graph->createVertex('v2'));
  155. $graph->getVertex('v2')->createEdge($graph->createVertex('v3'));
  156. $graph->getVertex('v3')->createEdgeTo($graph->createVertex('v4'));
  157. $tree = $this->createTreeAlg($graph);
  158. $this->assertFalse($tree->isTree());
  159. }
  160. }