public function Graph::searchAndSort

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

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