diff options
| -rw-r--r-- | includes/graph.inc | 16 | ||||
| -rw-r--r-- | includes/module.inc | 2 | ||||
| -rw-r--r-- | modules/simpletest/tests/graph.test | 12 |
3 files changed, 19 insertions, 11 deletions
diff --git a/includes/graph.inc b/includes/graph.inc index 38b2abb1c..e9fffc587 100644 --- a/includes/graph.inc +++ b/includes/graph.inc @@ -121,19 +121,23 @@ function _drupal_depth_first_search(&$graph, &$state, $start, &$component = NULL unset($state['components'][$component]); $component = $new_component; } + // Only visit existing vertices. + if (isset($graph[$end])) { + // Visit the connected vertex. + _drupal_depth_first_search($graph, $state, $end, $component); - // Visit the connected vertex. - _drupal_depth_first_search($graph, $state, $end, $component); - - // All vertices reachable by $end are also reachable by $start. - $graph[$start]['paths'] += $graph[$end]['paths']; + // All vertices reachable by $end are also reachable by $start. + $graph[$start]['paths'] += $graph[$end]['paths']; + } } } // Now that any other subgraph has been explored, add $start to all reverse // paths. foreach ($graph[$start]['paths'] as $end => $v) { - $graph[$end]['reverse_paths'][$start] = TRUE; + if (isset($graph[$end])) { + $graph[$end]['reverse_paths'][$start] = TRUE; + } } // Record the order of the last visit. This is the reverse of the diff --git a/includes/module.inc b/includes/module.inc index 71db71f57..dbe51279b 100644 --- a/includes/module.inc +++ b/includes/module.inc @@ -170,7 +170,7 @@ function _module_build_dependencies($files) { } drupal_depth_first_search($graph, array_keys($roots)); foreach ($graph as $module => $data) { - $files[$module]->required_by= isset($data['reverse_paths']) ? $data['reverse_paths'] : array(); + $files[$module]->required_by = isset($data['reverse_paths']) ? $data['reverse_paths'] : array(); $files[$module]->requires = isset($data['paths']) ? $data['paths'] : array(); $files[$module]->sort = $data['weight']; } diff --git a/modules/simpletest/tests/graph.test b/modules/simpletest/tests/graph.test index cd88c2ee2..a6dac87ef 100644 --- a/modules/simpletest/tests/graph.test +++ b/modules/simpletest/tests/graph.test @@ -39,6 +39,7 @@ class GraphUnitTest extends DrupalWebTestCase { 5 => array(6), 7 => array(4, 5), 8 => array(9), + 9 => array(), )); drupal_depth_first_search($graph); @@ -48,7 +49,6 @@ class GraphUnitTest extends DrupalWebTestCase { 3 => array(), 4 => array(3), 5 => array(6), - 6 => array(), 7 => array(4, 3, 5, 6), 8 => array(9), 9 => array(), @@ -61,15 +61,17 @@ class GraphUnitTest extends DrupalWebTestCase { 3 => array(2, 1, 4, 7), 4 => array(2, 1, 7), 5 => array(7), - 6 => array(5, 7), 7 => array(), 8 => array(), 9 => array(8), ); $this->assertReversePaths($graph, $expected_reverse_paths); + // Assert that DFS didn't created "missing" vertexes automatically. + $this->assertFALSE(isset($graph[6]), t('Vertex 6 has not been created')); + $expected_components = array( - array(1, 2, 3, 4, 5, 6, 7), + array(1, 2, 3, 4, 5, 7), array(8, 9), ); $this->assertComponents($graph, $expected_components); @@ -78,7 +80,7 @@ class GraphUnitTest extends DrupalWebTestCase { array(1, 2, 3), array(2, 4, 3), array(7, 4, 3), - array(7, 5, 6), + array(7, 5), array(8, 9), ); $this->assertWeights($graph, $expected_weights); @@ -90,6 +92,8 @@ class GraphUnitTest extends DrupalWebTestCase { function normalizeGraph($graph) { $normalized_graph = array(); foreach ($graph as $vertex => $edges) { + // Create vertex even if it hasn't any edges. + $normalized_graph[$vertex] = array(); foreach ($edges as $edge) { $normalized_graph[$vertex]['edges'][$edge] = TRUE; } |