public Graph::searchAndSort()
Performs a depth-first search and sort on the directed acyclic graph.
Return value
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\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 | public function searchAndSort() { $state = array( // 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' => array(), // The components of the graph. 'components' => array(), ); // 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 = array(); 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;} |
Please login to continue.