Same name in other branches

1. 9 core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::depthFirstSearch()
2. 8.9.x core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::depthFirstSearch()
3. 11.x core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::depthFirstSearch()

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()

1 call to Graph::depthFirstSearch()

Graph::searchAndSort in core/lib/Drupal/Component/Graph/Graph.php

Performs a depth-first 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\Graph

Code

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;
}

---