protected Graph::depthFirstSearch(&$state, $start, &$component = NULL)
Performs a depth-first 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()
File
- core/lib/Drupal/Component/Graph/Graph.php, line 101
Class
- Graph
- Directed acyclic graph manipulation.
Namespace
Drupal\Component\Graph
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | 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'] = array(); // 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;} |
Please login to continue.