UndirectedTest.php 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
  1. <?php
  2. use Fhaculty\Graph\Graph;
  3. use Graphp\Algorithms\Tree\Undirected;
  4. class UndirectedTest extends TestCase
  5. {
  6. protected function createTree(Graph $graph)
  7. {
  8. return new Undirected($graph);
  9. }
  10. public function testNullGraph()
  11. {
  12. $graph = new Graph();
  13. $tree = $this->createTree($graph);
  14. $this->assertFalse($tree->isTree());
  15. $this->assertTrue($tree->getVerticesInternal()->isEmpty());
  16. $this->assertTrue($tree->getVerticesLeaf()->isEmpty());
  17. }
  18. public function testGraphTrivial()
  19. {
  20. $graph = new Graph();
  21. $graph->createVertex('v1');
  22. $tree = $this->createTree($graph);
  23. $this->assertTrue($tree->isTree());
  24. $this->assertSame(array(), $tree->getVerticesInternal()->getVector());
  25. $this->assertSame(array(), $tree->getVerticesLeaf()->getVector());
  26. }
  27. public function testGraphSimplePair()
  28. {
  29. // v1 -- v2
  30. $graph = new Graph();
  31. $graph->createVertex('v1')->createEdge($graph->createVertex('v2'));
  32. $tree = $this->createTree($graph);
  33. $this->assertTrue($tree->isTree());
  34. $this->assertSame(array(), $tree->getVerticesInternal()->getVector());
  35. $this->assertSame($graph->getVertices()->getVector(), $tree->getVerticesLeaf()->getVector());
  36. }
  37. public function testGraphSimpleLine()
  38. {
  39. // v1 -- v2 -- v3
  40. $graph = new Graph();
  41. $graph->createVertex('v1')->createEdge($graph->createVertex('v2'));
  42. $graph->getVertex('v2')->createEdge($graph->createVertex('v3'));
  43. $tree = $this->createTree($graph);
  44. $this->assertTrue($tree->isTree());
  45. $this->assertSame(array($graph->getVertex('v2')), $tree->getVerticesInternal()->getVector());
  46. $this->assertSame(array($graph->getVertex('v1'), $graph->getVertex('v3')), $tree->getVerticesLeaf()->getVector());
  47. }
  48. public function testGraphPairParallelIsNotTree()
  49. {
  50. // v1 -- v2 -- v1
  51. $graph = new Graph();
  52. $graph->createVertex('v1')->createEdge($graph->createVertex('v2'));
  53. $graph->getVertex('v1')->createEdge($graph->getVertex('v2'));
  54. $tree = $this->createTree($graph);
  55. $this->assertFalse($tree->isTree());
  56. }
  57. public function testGraphLoopIsNotTree()
  58. {
  59. // v1 -- v1
  60. $graph = new Graph();
  61. $graph->createVertex('v1')->createEdge($graph->getVertex('v1'));
  62. $tree = $this->createTree($graph);
  63. $this->assertFalse($tree->isTree());
  64. }
  65. public function testGraphCycleIsNotTree()
  66. {
  67. // v1 -- v2 -- v3 -- v1
  68. $graph = new Graph();
  69. $graph->createVertex('v1')->createEdge($graph->createVertex('v2'));
  70. $graph->getVertex('v2')->createEdge($graph->createVertex('v3'));
  71. $graph->getVertex('v3')->createEdge($graph->getVertex('v1'));
  72. $tree = $this->createTree($graph);
  73. $this->assertFalse($tree->isTree());
  74. }
  75. public function testGraphDirectedIsNotTree()
  76. {
  77. // v1 -> v2
  78. $graph = new Graph();
  79. $graph->createVertex('v1')->createEdgeTo($graph->createVertex('v2'));
  80. $tree = $this->createTree($graph);
  81. $this->assertFalse($tree->isTree());
  82. }
  83. public function testGraphMixedIsNotTree()
  84. {
  85. // v1 -- v2 -> v3
  86. $graph = new Graph();
  87. $graph->createVertex('v1')->createEdge($graph->createVertex('v2'));
  88. $graph->getVertex('v2')->createEdgeTo($graph->createVertex('v3'));
  89. $tree = $this->createTree($graph);
  90. $this->assertFalse($tree->isTree());
  91. }
  92. }