ParallelTest.php 3.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
  1. <?php
  2. use Graphp\Algorithms\Parallel as AlgorithmParallel;
  3. use Fhaculty\Graph\Graph;
  4. class ParallelTest extends TestCase
  5. {
  6. public function testGraphEmpty()
  7. {
  8. $graph = new Graph();
  9. $alg = new AlgorithmParallel($graph);
  10. $this->assertFalse($alg->hasEdgeParallel());
  11. }
  12. public function testDirectedCycleIsNotConsideredParallel()
  13. {
  14. // 1 -> 2
  15. // 2 -> 1
  16. $graph = new Graph();
  17. $v1 = $graph->createVertex(1);
  18. $v2 = $graph->createVertex(2);
  19. $e1 = $v1->createEdgeTo($v2);
  20. $e2 = $v2->createEdgeTo($v1);
  21. $alg = new AlgorithmParallel($graph);
  22. $this->assertFalse($alg->hasEdgeParallel());
  23. $this->assertEquals(array(), $alg->getEdgesParallelEdge($e1)->getVector());
  24. $this->assertEquals(array(), $alg->getEdgesParallelEdge($e2)->getVector());
  25. }
  26. public function testDirectedParallelEdge()
  27. {
  28. // 1 -> 2
  29. // 1 -> 2
  30. $graph = new Graph();
  31. $v1 = $graph->createVertex(1);
  32. $v2 = $graph->createVertex(2);
  33. $e1 = $v1->createEdgeTo($v2);
  34. $e2 = $v1->createEdgeTo($v2);
  35. $alg = new AlgorithmParallel($graph);
  36. $this->assertTrue($alg->hasEdgeParallel());
  37. $this->assertEquals(array($e2), $alg->getEdgesParallelEdge($e1)->getVector());
  38. $this->assertEquals(array($e1), $alg->getEdgesParallelEdge($e2)->getVector());
  39. }
  40. public function testMixedParallelEdge()
  41. {
  42. // 1 -> 2
  43. // 1 -- 2
  44. $graph = new Graph();
  45. $v1 = $graph->createVertex(1);
  46. $v2 = $graph->createVertex(2);
  47. $e1 = $v1->createEdgeTo($v2);
  48. $e2 = $v1->createEdge($v2);
  49. $alg = new AlgorithmParallel($graph);
  50. $this->assertTrue($alg->hasEdgeParallel());
  51. $this->assertEquals(array($e2), $alg->getEdgesParallelEdge($e1)->getVector());
  52. $this->assertEquals(array($e1), $alg->getEdgesParallelEdge($e2)->getVector());
  53. }
  54. public function testMixedParallelEdgesMultiple()
  55. {
  56. // 1 -> 2
  57. // 1 -> 2
  58. // 1 -- 2
  59. // 1 -- 2
  60. // 2 -> 1
  61. // 2 -> 1
  62. $graph = new Graph();
  63. $v1 = $graph->createVertex(1);
  64. $v2 = $graph->createVertex(2);
  65. $e1 = $v1->createEdgeTo($v2);
  66. $e2 = $v1->createEdgeTo($v2);
  67. $e3 = $v1->createEdge($v2);
  68. $e4 = $v1->createEdge($v2);
  69. $e5 = $v2->createEdgeTo($v1);
  70. $e6 = $v2->createEdgeTo($v1);
  71. $alg = new AlgorithmParallel($graph);
  72. $this->assertTrue($alg->hasEdgeParallel());
  73. $this->assertEquals(array($e2, $e3, $e4), $alg->getEdgesParallelEdge($e1)->getVector());
  74. $this->assertEquals(array($e1, $e3, $e4), $alg->getEdgesParallelEdge($e2)->getVector());
  75. $this->assertEquals(array($e1, $e2, $e4, $e5, $e6), $alg->getEdgesParallelEdge($e3)->getVector());
  76. $this->assertEquals(array($e1, $e2, $e3, $e5, $e6), $alg->getEdgesParallelEdge($e4)->getVector());
  77. $this->assertEquals(array($e3, $e4, $e6), $alg->getEdgesParallelEdge($e5)->getVector());
  78. $this->assertEquals(array($e3, $e4, $e5), $alg->getEdgesParallelEdge($e6)->getVector());
  79. }
  80. }