function Graph::searchAndSort
Same name in other branches
 9 core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::searchAndSort()
 8.9.x core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::searchAndSort()
 11.x core/lib/Drupal/Component/Graph/Graph.php \Drupal\Component\Graph\Graph::searchAndSort()
Performs a depthfirst search and sort on the directed acyclic graph.
Return value
array The given $graph with more secondary keys filled in:
 'paths': Contains a list of vertices than can be reached on a path from this vertex.
 'reverse_paths': Contains a list of vertices that has a path from them to this vertex.
 'weight': If there is a path from a vertex to another then the weight of the latter is higher.
 'component': Vertices in the same component have the same component identifier.
File

core/
lib/ Drupal/ Component/ Graph/ Graph.php, line 58
Class
 Graph
 Directed acyclic graph manipulation.
Namespace
Drupal\Component\GraphCode
public function searchAndSort() {
$state = [
// The order of last visit of the depth first search. This is the reverse
// of the topological order if the graph is acyclic.
'last_visit_order' => [],
// The components of the graph.
'components' => [],
];
// Perform the actual search.
foreach ($this>graph as $start => $data) {
$this>depthFirstSearch($state, $start);
}
// We do such a numbering that every component starts with 0. This is useful
// for module installs as we can install every 0 weighted module in one
// request, and then every 1 weighted etc.
$component_weights = [];
foreach ($state['last_visit_order'] as $vertex) {
$component = $this>graph[$vertex]['component'];
if (!isset($component_weights[$component])) {
$component_weights[$component] = 0;
}
$this>graph[$vertex]['weight'] = $component_weights[$component];
}
return $this>graph;
}
Buggy or inaccurate documentation? Please file an issue. Need support? Need help programming? Connect with the Drupal community.