ConnectedComponentsTest.php 2.8 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
  1. <?php
  2. use Graphp\Algorithms\ConnectedComponents as AlgorithmConnected;
  3. use Fhaculty\Graph\Graph;
  4. class ConnectedComponentsTest extends TestCase
  5. {
  6. public function testNullGraph()
  7. {
  8. $graph = new Graph();
  9. $alg = new AlgorithmConnected($graph);
  10. $this->assertEquals(0, $alg->getNumberOfComponents());
  11. $this->assertFalse($alg->isSingle());
  12. $this->assertCount(0, $alg->createGraphsComponents());
  13. }
  14. public function testGraphSingleTrivial()
  15. {
  16. $graph = new Graph();
  17. $graph->createVertex(1);
  18. $alg = new AlgorithmConnected($graph);
  19. $this->assertEquals(1, $alg->getNumberOfComponents());
  20. $this->assertTrue($alg->isSingle());
  21. $graphs = $alg->createGraphsComponents();
  22. $this->assertCount(1, $graphs);
  23. $this->assertGraphEquals($graph, reset($graphs));
  24. }
  25. public function testGraphEdgeDirections()
  26. {
  27. // 1 -- 2 -> 3 <- 4
  28. $graph = new Graph();
  29. $graph->createVertex(1)->createEdge($graph->createVertex(2));
  30. $graph->getVertex(2)->createEdgeTo($graph->createVertex(3));
  31. $graph->createVertex(4)->createEdgeTo($graph->getVertex(3));
  32. $alg = new AlgorithmConnected($graph);
  33. $this->assertEquals(1, $alg->getNumberOfComponents());
  34. $this->assertTrue($alg->isSingle());
  35. $graphs = $alg->createGraphsComponents();
  36. $this->assertCount(1, $graphs);
  37. $this->assertGraphEquals($graph, reset($graphs));
  38. $this->assertGraphEquals($graph, $alg->createGraphComponentVertex($graph->getVertex(1)));
  39. }
  40. public function testComponents()
  41. {
  42. // 1 -- 2, 3 -> 4, 5
  43. $graph = new Graph();
  44. $v1 = $graph->createVertex(1);
  45. $v2 = $graph->createVertex(2);
  46. $v3 = $graph->createVertex(3);
  47. $v4 = $graph->createVertex(4);
  48. $v5 = $graph->createVertex(5);
  49. $e1 = $v1->createEdge($v2);
  50. $e2 = $v3->createEdgeTo($v4);
  51. $alg = new AlgorithmConnected($graph);
  52. $this->assertEquals(3, $alg->getNumberOfComponents());
  53. $this->assertFalse($alg->isSingle());
  54. $graphs = $alg->createGraphsComponents();
  55. $this->assertCount(3, $graphs);
  56. $ge = new Graph();
  57. $ge->createVertex(1)->createEdge($ge->createVertex(2));
  58. $this->assertGraphEquals($ge, $alg->createGraphComponentVertex($v2));
  59. $ge = new Graph();
  60. $ge->createVertex(5);
  61. $this->assertEquals($ge, $alg->createGraphComponentVertex($v5));
  62. }
  63. /**
  64. * @expectedException InvalidArgumentException
  65. */
  66. public function testInvalidVertexPassedToAlgorithm()
  67. {
  68. $graph = new Graph();
  69. $graph2 = new Graph();
  70. $v2 = $graph2->createVertex(12);
  71. $alg = new AlgorithmConnected($graph);
  72. $alg->createGraphComponentVertex($v2);
  73. }
  74. }