WalkPropertyTest.php 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186
  1. <?php
  2. use Fhaculty\Graph\Walk;
  3. use Fhaculty\Graph\Graph;
  4. use Graphp\Algorithms\Property\WalkProperty;
  5. class WalkPropertyTest extends TestCase
  6. {
  7. public function testTrivialGraph()
  8. {
  9. $graph = new Graph();
  10. $v1 = $graph->createVertex(1);
  11. $walk = Walk::factoryFromEdges(array(), $v1);
  12. $this->assertEquals(1, count($walk->getVertices()));
  13. $this->assertEquals(0, count($walk->getEdges()));
  14. $alg = new WalkProperty($walk);
  15. $this->assertFalse($alg->isLoop());
  16. $this->assertFalse($alg->hasLoop());
  17. $this->assertFalse($alg->isCycle());
  18. $this->assertFalse($alg->hasCycle());
  19. $this->assertTrue($alg->isPath());
  20. $this->assertTrue($alg->isSimple());
  21. $this->assertTrue($alg->isEulerian());
  22. $this->assertTrue($alg->isHamiltonian());
  23. }
  24. public function testLoop()
  25. {
  26. // 1 -- 1
  27. $graph = new Graph();
  28. $v1 = $graph->createVertex(1);
  29. $e1 = $v1->createEdge($v1);
  30. $walk = Walk::factoryFromEdges(array($e1), $v1);
  31. $alg = new WalkProperty($walk);
  32. $this->assertTrue($alg->isLoop());
  33. $this->assertTrue($alg->hasLoop());
  34. $this->assertTrue($alg->isCycle());
  35. $this->assertTrue($alg->hasCycle());
  36. $this->assertTrue($alg->isPath());
  37. $this->assertTrue($alg->isSimple());
  38. $this->assertTrue($alg->isEulerian());
  39. $this->assertTrue($alg->isHamiltonian());
  40. }
  41. public function testCycle()
  42. {
  43. // 1 -- 2 -- 1
  44. $graph = new Graph();
  45. $v1 = $graph->createVertex(1);
  46. $v2 = $graph->createVertex(2);
  47. $e1 = $v1->createEdge($v2);
  48. $e2 = $v2->createEdge($v1);
  49. $walk = Walk::factoryFromEdges(array($e1, $e2), $v1);
  50. $this->assertEquals(3, count($walk->getVertices()));
  51. $this->assertEquals(2, count($walk->getEdges()));
  52. $alg = new WalkProperty($walk);
  53. $this->assertTrue($alg->isCycle());
  54. $this->assertTrue($alg->hasCycle());
  55. $this->assertTrue($alg->isPath());
  56. $this->assertTrue($alg->isSimple());
  57. $this->assertTrue($alg->isEulerian());
  58. $this->assertTrue($alg->isHamiltonian());
  59. }
  60. public function testCircuit()
  61. {
  62. // 1 -> 2 -> 1, 2 -> 2
  63. $graph = new Graph();
  64. $v1 = $graph->createVertex(1);
  65. $v2 = $graph->createVertex(2);
  66. $e1 = $v1->createEdgeTo($v2);
  67. $e2 = $v2->createEdgeTo($v1);
  68. $e3 = $v2->createEdgeTo($v2);
  69. // 1 -> 2 -> 2 -> 1
  70. $walk = Walk::factoryFromEdges(array($e1, $e3, $e2), $v1);
  71. $this->assertEquals(array(1, 2, 2, 1), $walk->getVertices()->getIds());
  72. $alg = new WalkProperty($walk);
  73. $this->assertTrue($alg->isCycle());
  74. $this->assertTrue($alg->isCircuit());
  75. }
  76. public function testNonCircuit()
  77. {
  78. // 1 -> 2 -> 1, 2 -> 2
  79. $graph = new Graph();
  80. $v1 = $graph->createVertex(1);
  81. $v2 = $graph->createVertex(2);
  82. $e1 = $v1->createEdgeTo($v2);
  83. $e2 = $v2->createEdgeTo($v1);
  84. $e3 = $v2->createEdgeTo($v2);
  85. // non-circuit: taking loop twice
  86. // 1 -> 2 -> 2 -> 2 -> 1
  87. $walk = Walk::factoryFromEdges(array($e1, $e3, $e3, $e2), $v1);
  88. $this->assertEquals(array(1, 2, 2, 2, 1), $walk->getVertices()->getIds());
  89. $alg = new WalkProperty($walk);
  90. $this->assertTrue($alg->isCycle());
  91. $this->assertFalse($alg->isCircuit());
  92. }
  93. public function testDigon()
  94. {
  95. // 1 -> 2 -> 1
  96. $graph = new Graph();
  97. $v1 = $graph->createVertex(1);
  98. $v2 = $graph->createVertex(2);
  99. $e1 = $v1->createEdgeTo($v2);
  100. $e2 = $v2->createEdgeTo($v1);
  101. $walk = Walk::factoryFromEdges(array($e1, $e2), $v1);
  102. $alg = new WalkProperty($walk);
  103. $this->assertTrue($alg->isDigon());
  104. }
  105. public function testTriangle()
  106. {
  107. // 1 -> 2 -> 3 -> 1
  108. $graph = new Graph();
  109. $v1 = $graph->createVertex(1);
  110. $v2 = $graph->createVertex(2);
  111. $v3 = $graph->createVertex(3);
  112. $e1 = $v1->createEdgeTo($v2);
  113. $e2 = $v2->createEdgeTo($v3);
  114. $e3 = $v3->createEdgeTo($v1);
  115. $walk = Walk::factoryFromEdges(array($e1, $e2, $e3), $v1);
  116. $alg = new WalkProperty($walk);
  117. $this->assertTrue($alg->isTriangle());
  118. }
  119. public function testSimplePathWithinGraph()
  120. {
  121. // 1 -- 2 -- 2
  122. $graph = new Graph();
  123. $v1 = $graph->createVertex(1);
  124. $v2 = $graph->createVertex(2);
  125. $e1 = $v1->createEdge($v2);
  126. $e2 = $v2->createEdge($v2);
  127. // only use "2 -- 2" part
  128. $walk = Walk::factoryFromEdges(array($e2), $v2);
  129. $this->assertEquals(2, count($walk->getVertices()));
  130. $this->assertEquals(1, count($walk->getEdges()));
  131. $alg = new WalkProperty($walk);
  132. $this->assertTrue($alg->isCycle());
  133. $this->assertTrue($alg->hasCycle());
  134. $this->assertTrue($alg->isPath());
  135. $this->assertTrue($alg->isSimple());
  136. $this->assertFalse($alg->isEulerian());
  137. $this->assertFalse($alg->isHamiltonian());
  138. }
  139. }