diff --git a/core/modules/system/lib/Drupal/system/Tests/Graph/GraphUnitTest.php b/core/modules/system/lib/Drupal/system/Tests/Graph/GraphUnitTest.php index a68535c..0a64512 100644 --- a/core/modules/system/lib/Drupal/system/Tests/Graph/GraphUnitTest.php +++ b/core/modules/system/lib/Drupal/system/Tests/Graph/GraphUnitTest.php @@ -16,6 +16,7 @@ * @see Drupal\Component\Graph\Graph */ class GraphUnitTest extends UnitTestBase { + public static function getInfo() { return array( 'name' => 'Directed acyclic graph manipulation', @@ -71,11 +72,12 @@ function testDepthFirstSearch() { ); $this->assertReversePaths($graph, $expected_reverse_paths); - // Assert that DFS didn't created "missing" vertexes automatically. - $this->assertFALSE(isset($graph[6]), 'Vertex 6 has not been created'); + // Assert target vertice 6 only has 'unlisted_sink' + $this->assertTRUE(isset($graph[6]), 'Vertex 6 has been created'); + $this->assertTRUE(isset($graph[6]['unlisted_sink']), 'Vertex 6 is marked as unlisted_sink'); $expected_components = array( - array(1, 2, 3, 4, 5, 7), + array(1, 2, 3, 4, 5, 6, 7), array(8, 9), ); $this->assertComponents($graph, $expected_components); @@ -90,6 +92,36 @@ function testDepthFirstSearch() { $this->assertWeights($graph, $expected_weights); } + function testGraphNormalized() { + $g = array(); + // a -> b -> c + $g['a']['edges']['b'] = 1; + $g['b']['edges']['c'] = 1; + + // disjunct f -> g + $g['f']['edges']['g'] = 1; + + // disjunct p -> q + $g['p']['edges']['q'] = 1; + + // A bypass a -> c + $g['a']['edges']['c'] = 1; + + $graph_object = new Graph($g); + $sorted_graph = $graph_object->searchAndSort(); + + $this->assertTrue(isset($sorted_graph['c']), 'Vertice C is added to the GraphNormalized'); + + $tsl = $graph_object->getTopologicalSortedList(); + $dummy = $tsl; + + $head = array_shift($dummy); + $this->assertTrue(in_array($head, array('a', 'f', 'p')), "The TSL starts with a, f or p: " . join(', ', $tsl)); + + $tail = array_pop($dummy); + $this->assertTrue(in_array($tail, array('c', 'g', 'q')), "The TSL ends with c, g or q: " . join(', ', $tsl)); + } + /** * Return a normalized version of a graph. */ @@ -195,4 +227,5 @@ function displayArray($paths, $keys = FALSE) { return '(empty)'; } } + }