123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186 |
- <?php
- use Fhaculty\Graph\Walk;
- use Fhaculty\Graph\Graph;
- use Graphp\Algorithms\Property\WalkProperty;
- class WalkPropertyTest extends TestCase
- {
- public function testTrivialGraph()
- {
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $walk = Walk::factoryFromEdges(array(), $v1);
- $this->assertEquals(1, count($walk->getVertices()));
- $this->assertEquals(0, count($walk->getEdges()));
- $alg = new WalkProperty($walk);
- $this->assertFalse($alg->isLoop());
- $this->assertFalse($alg->hasLoop());
- $this->assertFalse($alg->isCycle());
- $this->assertFalse($alg->hasCycle());
- $this->assertTrue($alg->isPath());
- $this->assertTrue($alg->isSimple());
- $this->assertTrue($alg->isEulerian());
- $this->assertTrue($alg->isHamiltonian());
- }
- public function testLoop()
- {
- // 1 -- 1
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $e1 = $v1->createEdge($v1);
- $walk = Walk::factoryFromEdges(array($e1), $v1);
- $alg = new WalkProperty($walk);
- $this->assertTrue($alg->isLoop());
- $this->assertTrue($alg->hasLoop());
- $this->assertTrue($alg->isCycle());
- $this->assertTrue($alg->hasCycle());
- $this->assertTrue($alg->isPath());
- $this->assertTrue($alg->isSimple());
- $this->assertTrue($alg->isEulerian());
- $this->assertTrue($alg->isHamiltonian());
- }
- public function testCycle()
- {
- // 1 -- 2 -- 1
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $e1 = $v1->createEdge($v2);
- $e2 = $v2->createEdge($v1);
- $walk = Walk::factoryFromEdges(array($e1, $e2), $v1);
- $this->assertEquals(3, count($walk->getVertices()));
- $this->assertEquals(2, count($walk->getEdges()));
- $alg = new WalkProperty($walk);
- $this->assertTrue($alg->isCycle());
- $this->assertTrue($alg->hasCycle());
- $this->assertTrue($alg->isPath());
- $this->assertTrue($alg->isSimple());
- $this->assertTrue($alg->isEulerian());
- $this->assertTrue($alg->isHamiltonian());
- }
- public function testCircuit()
- {
- // 1 -> 2 -> 1, 2 -> 2
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $e1 = $v1->createEdgeTo($v2);
- $e2 = $v2->createEdgeTo($v1);
- $e3 = $v2->createEdgeTo($v2);
- // 1 -> 2 -> 2 -> 1
- $walk = Walk::factoryFromEdges(array($e1, $e3, $e2), $v1);
- $this->assertEquals(array(1, 2, 2, 1), $walk->getVertices()->getIds());
- $alg = new WalkProperty($walk);
- $this->assertTrue($alg->isCycle());
- $this->assertTrue($alg->isCircuit());
- }
- public function testNonCircuit()
- {
- // 1 -> 2 -> 1, 2 -> 2
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $e1 = $v1->createEdgeTo($v2);
- $e2 = $v2->createEdgeTo($v1);
- $e3 = $v2->createEdgeTo($v2);
- // non-circuit: taking loop twice
- // 1 -> 2 -> 2 -> 2 -> 1
- $walk = Walk::factoryFromEdges(array($e1, $e3, $e3, $e2), $v1);
- $this->assertEquals(array(1, 2, 2, 2, 1), $walk->getVertices()->getIds());
- $alg = new WalkProperty($walk);
- $this->assertTrue($alg->isCycle());
- $this->assertFalse($alg->isCircuit());
- }
- public function testDigon()
- {
- // 1 -> 2 -> 1
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $e1 = $v1->createEdgeTo($v2);
- $e2 = $v2->createEdgeTo($v1);
- $walk = Walk::factoryFromEdges(array($e1, $e2), $v1);
- $alg = new WalkProperty($walk);
- $this->assertTrue($alg->isDigon());
- }
- public function testTriangle()
- {
- // 1 -> 2 -> 3 -> 1
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $v3 = $graph->createVertex(3);
- $e1 = $v1->createEdgeTo($v2);
- $e2 = $v2->createEdgeTo($v3);
- $e3 = $v3->createEdgeTo($v1);
- $walk = Walk::factoryFromEdges(array($e1, $e2, $e3), $v1);
- $alg = new WalkProperty($walk);
- $this->assertTrue($alg->isTriangle());
- }
- public function testSimplePathWithinGraph()
- {
- // 1 -- 2 -- 2
- $graph = new Graph();
- $v1 = $graph->createVertex(1);
- $v2 = $graph->createVertex(2);
- $e1 = $v1->createEdge($v2);
- $e2 = $v2->createEdge($v2);
- // only use "2 -- 2" part
- $walk = Walk::factoryFromEdges(array($e2), $v2);
- $this->assertEquals(2, count($walk->getVertices()));
- $this->assertEquals(1, count($walk->getEdges()));
- $alg = new WalkProperty($walk);
- $this->assertTrue($alg->isCycle());
- $this->assertTrue($alg->hasCycle());
- $this->assertTrue($alg->isPath());
- $this->assertTrue($alg->isSimple());
- $this->assertFalse($alg->isEulerian());
- $this->assertFalse($alg->isHamiltonian());
- }
- }
|