function Graph::depthFirstSearch
Same name in other branches
 9 core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::depthFirstSearch()
 8.9.x core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::depthFirstSearch()
 11.x core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::depthFirstSearch()
Performs a depthfirst search on a graph.
Parameters
$state: An associative array. The key 'last_visit_order' stores a list of the vertices visited. The key components stores list of vertices belonging to the same the component.
$start: An arbitrary vertex where we started traversing the graph.
$component: The component of the last vertex.
See also
\Drupal\Component\Graph\Graph::searchAndSort()
1 call to Graph::depthFirstSearch()
 Graph::searchAndSort in core/
lib/ Drupal/ Component/ Graph/ Graph.php  Performs a depthfirst search and sort on the directed acyclic graph.
File

core/
lib/ Drupal/ Component/ Graph/ Graph.php, line 101
Class
 Graph
 Directed acyclic graph manipulation.
Namespace
Drupal\Component\GraphCode
protected function depthFirstSearch(&$state, $start, &$component = NULL) {
// Assign new component for each new vertex, i.e. when not called recursively.
if (!isset($component)) {
$component = $start;
}
// Nothing to do, if we already visited this vertex.
if (isset($this>graph[$start]['paths'])) {
return;
}
// Mark $start as visited.
$this>graph[$start]['paths'] = [];
// Assign $start to the current component.
$this>graph[$start]['component'] = $component;
$state['components'][$component][] = $start;
// Visit edges of $start.
if (isset($this>graph[$start]['edges'])) {
foreach ($this>graph[$start]['edges'] as $end => $v) {
// Mark that $start can reach $end.
$this>graph[$start]['paths'][$end] = $v;
if (isset($this>graph[$end]['component']) && $component != $this>graph[$end]['component']) {
// This vertex already has a component, use that from now on and
// reassign all the previously explored vertices.
$new_component = $this>graph[$end]['component'];
foreach ($state['components'][$component] as $vertex) {
$this>graph[$vertex]['component'] = $new_component;
$state['components'][$new_component][] = $vertex;
}
unset($state['components'][$component]);
$component = $new_component;
}
// Only visit existing vertices.
if (isset($this>graph[$end])) {
// Visit the connected vertex.
$this>depthFirstSearch($state, $end, $component);
// All vertices reachable by $end are also reachable by $start.
$this>graph[$start]['paths'] += $this>graph[$end]['paths'];
}
}
}
// Now that any other subgraph has been explored, add $start to all reverse
// paths.
foreach ($this>graph[$start]['paths'] as $end => $v) {
if (isset($this>graph[$end])) {
$this>graph[$end]['reverse_paths'][$start] = $v;
}
}
// Record the order of the last visit. This is the reverse of the
// topological order if the graph is acyclic.
$state['last_visit_order'][] = $start;
}
Buggy or inaccurate documentation? Please file an issue. Need support? Need help programming? Connect with the Drupal community.