BreadthFirstTest.php 1.1 KB

1234567891011121314151617181920212223242526272829303132333435363738
  1. <?php
  2. use Fhaculty\Graph\Graph;
  3. use Fhaculty\Graph\Vertex;
  4. use Graphp\Algorithms\ShortestPath\BreadthFirst;
  5. class BreadthFirstTest extends BaseShortestPathTest
  6. {
  7. protected function createAlg(Vertex $vertex)
  8. {
  9. return new BreadthFirst($vertex);
  10. }
  11. public function testGraphParallelNegative()
  12. {
  13. // 1 -[10]-> 2
  14. // 1 -[-1]-> 2
  15. $graph = new Graph();
  16. $v1 = $graph->createVertex(1);
  17. $v2 = $graph->createVertex(2);
  18. $e1 = $v1->createEdgeTo($v2)->setWeight(10);
  19. $e2 = $v1->createEdgeTo($v2)->setWeight(-1);
  20. $alg = $this->createAlg($v1);
  21. $this->assertEquals(1, $alg->getDistance($v2));
  22. $this->assertEquals(array(2 => 1), $alg->getDistanceMap());
  23. $this->assertEquals(array($e1), $alg->getEdges()->getVector());
  24. $this->assertEquals(array($e1), $alg->getEdgesTo($v2)->getVector());
  25. $this->assertEquals(array(2 => $v2), $alg->getVertices()->getMap());
  26. $this->assertEquals(array(2), $alg->getVertices()->getIds());
  27. }
  28. protected function getExpectedWeight($edges)
  29. {
  30. return count($edges);
  31. }
  32. }