TopologicalSortTest.php 2.0 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
  1. <?php
  2. use Graphp\Algorithms\TopologicalSort;
  3. use Fhaculty\Graph\Exception\UnexpectedValueException;
  4. use Fhaculty\Graph\Edge\Base as Edge;
  5. use Fhaculty\Graph\Graph;
  6. class TopologicalSortTest extends TestCase
  7. {
  8. public function testGraphEmpty()
  9. {
  10. $graph = new Graph();
  11. $alg = new TopologicalSort($graph);
  12. $this->assertInstanceOf('Fhaculty\Graph\Set\Vertices', $alg->getVertices());
  13. $this->assertTrue($alg->getVertices()->isEmpty());
  14. }
  15. public function testGraphIsolated()
  16. {
  17. $graph = new Graph();
  18. $graph->createVertex(1);
  19. $graph->createVertex(2);
  20. $alg = new TopologicalSort($graph);
  21. $this->assertSame(array($graph->getVertex(1), $graph->getVertex(2)), $alg->getVertices()->getVector());
  22. }
  23. public function testGraphSimple()
  24. {
  25. $graph = new Graph();
  26. $graph->createVertex(1)->createEdgeTo($graph->createVertex(2));
  27. $alg = new TopologicalSort($graph);
  28. $this->assertSame(array($graph->getVertex(1), $graph->getVertex(2)), $alg->getVertices()->getVector());
  29. }
  30. /**
  31. * @expectedException UnexpectedValueException
  32. */
  33. public function testFailUndirected()
  34. {
  35. $graph = new Graph();
  36. $graph->createVertex(1)->createEdge($graph->createVertex(2));
  37. $alg = new TopologicalSort($graph);
  38. $alg->getVertices();
  39. }
  40. /**
  41. * @expectedException UnexpectedValueException
  42. */
  43. public function testFailLoop()
  44. {
  45. $graph = new Graph();
  46. $graph->createVertex(1)->createEdgeTo($graph->getVertex(1));
  47. $alg = new TopologicalSort($graph);
  48. $alg->getVertices();
  49. }
  50. /**
  51. * @expectedException UnexpectedValueException
  52. */
  53. public function testFailCycle()
  54. {
  55. $graph = new Graph();
  56. $graph->createVertex(1)->createEdgeTo($graph->createVertex(2));
  57. $graph->getVertex(2)->createEdgeTo($graph->getVertex(1));
  58. $alg = new TopologicalSort($graph);
  59. $alg->getVertices();
  60. }
  61. }