BipartitTest.php 2.6 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
  1. <?php
  2. use Graphp\Algorithms\Bipartit as AlgorithmBipartit;
  3. use Fhaculty\Graph\Graph;
  4. class BipartitTest extends TestCase
  5. {
  6. public function testGraphEmpty()
  7. {
  8. $graph = new Graph();
  9. $alg = new AlgorithmBipartit($graph);
  10. $this->assertTrue($alg->isBipartit());
  11. $this->assertEquals(array(), $alg->getColors());
  12. $this->assertEquals(array(0 => array(), 1 => array()), $alg->getColorVertices());
  13. }
  14. public function testGraphPairIsBipartit()
  15. {
  16. // 1 -> 2
  17. $graph = new Graph();
  18. $v1 = $graph->createVertex(1);
  19. $v2 = $graph->createVertex(2);
  20. $v1->createEdgeTo($v2);
  21. $alg = new AlgorithmBipartit($graph);
  22. $this->assertTrue($alg->isBipartit());
  23. $this->assertEquals(array(1 => 0, 2 => 1), $alg->getColors());
  24. $this->assertEquals(array(0 => array(1 => $v1), 1 => array(2 => $v2)), $alg->getColorVertices());
  25. return $alg;
  26. }
  27. /**
  28. *
  29. * @param AlgorithmBipartit $alg
  30. * @depends testGraphPairIsBipartit
  31. */
  32. public function testGraphPairBipartitGroups(AlgorithmBipartit $alg)
  33. {
  34. // graph does not have any groups assigned, so its groups are not bipartit
  35. $this->assertFalse($alg->isBipartitGroups());
  36. // create a cloned graph with groups assigned according to bipartition
  37. $graph = $alg->createGraphGroups();
  38. $this->assertInstanceOf('Fhaculty\Graph\Graph', $graph);
  39. $alg2 = new AlgorithmBipartit($graph);
  40. $this->assertTrue($alg2->isBipartitGroups());
  41. }
  42. public function testGraphTriangleCycleIsNotBipartit()
  43. {
  44. // 1 -> 2 --> 3 --> 1
  45. $graph = new Graph();
  46. $v1 = $graph->createVertex(1);
  47. $v2 = $graph->createVertex(2);
  48. $v3 = $graph->createVertex(3);
  49. $v1->createEdgeTo($v2);
  50. $v2->createEdgeTo($v3);
  51. $v3->createEdgeTo($v1);
  52. $alg = new AlgorithmBipartit($graph);
  53. $this->assertFalse($alg->isBipartit());
  54. return $alg;
  55. }
  56. /**
  57. *
  58. * @param AlgorithmBipartit $alg
  59. * @expectedException UnexpectedValueException
  60. * @depends testGraphTriangleCycleIsNotBipartit
  61. */
  62. public function testGraphTriangleCycleColorsInvalid(AlgorithmBipartit $alg)
  63. {
  64. $alg->getColors();
  65. }
  66. /**
  67. *
  68. * @param AlgorithmBipartit $alg
  69. * @expectedException UnexpectedValueException
  70. * @depends testGraphTriangleCycleIsNotBipartit
  71. */
  72. public function testGraphTriangleCycleColorVerticesInvalid(AlgorithmBipartit $alg)
  73. {
  74. $alg->getColorVertices();
  75. }
  76. }