Chris@0: <?php
Chris@0: 
Chris@0: namespace Drupal\Component\Graph;
Chris@0: 
Chris@0: /**
Chris@0:  * Directed acyclic graph manipulation.
Chris@0:  */
Chris@0: class Graph {
Chris@0: 
Chris@0:   /**
Chris@0:    * Holds the directed acyclic graph.
Chris@0:    */
Chris@0:   protected $graph;
Chris@0: 
Chris@0:   /**
Chris@0:    * Instantiates the depth first search object.
Chris@0:    *
Chris@0:    * @param $graph
Chris@0:    *   A three dimensional associated array, with the first keys being the names
Chris@0:    *   of the vertices, these can be strings or numbers. The second key is
Chris@0:    *   'edges' and the third one are again vertices, each such key representing
Chris@0:    *   an edge. Values of array elements are copied over.
Chris@0:    *
Chris@0:    *   Example:
Chris@0:    *   @code
Chris@0:    *     $graph[1]['edges'][2] = 1;
Chris@0:    *     $graph[2]['edges'][3] = 1;
Chris@0:    *     $graph[2]['edges'][4] = 1;
Chris@0:    *     $graph[3]['edges'][4] = 1;
Chris@0:    *   @endcode
Chris@0:    *
Chris@0:    *   On return you will also have:
Chris@0:    *   @code
Chris@0:    *     $graph[1]['paths'][2] = 1;
Chris@0:    *     $graph[1]['paths'][3] = 1;
Chris@0:    *     $graph[2]['reverse_paths'][1] = 1;
Chris@0:    *     $graph[3]['reverse_paths'][1] = 1;
Chris@0:    *   @endcode
Chris@0:    */
Chris@0:   public function __construct($graph) {
Chris@0:     $this->graph = $graph;
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Performs a depth-first search and sort on the directed acyclic graph.
Chris@0:    *
Chris@0:    * @return
Chris@0:    *   The given $graph with more secondary keys filled in:
Chris@0:    *   - 'paths': Contains a list of vertices than can be reached on a path from
Chris@0:    *     this vertex.
Chris@0:    *   - 'reverse_paths': Contains a list of vertices that has a path from them
Chris@0:    *     to this vertex.
Chris@0:    *   - 'weight': If there is a path from a vertex to another then the weight of
Chris@0:    *     the latter is higher.
Chris@0:    *   - 'component': Vertices in the same component have the same component
Chris@0:    *     identifier.
Chris@0:    */
Chris@0:   public function searchAndSort() {
Chris@0:     $state = [
Chris@0:       // The order of last visit of the depth first search. This is the reverse
Chris@0:       // of the topological order if the graph is acyclic.
Chris@0:       'last_visit_order' => [],
Chris@0:       // The components of the graph.
Chris@0:       'components' => [],
Chris@0:     ];
Chris@0:     // Perform the actual search.
Chris@0:     foreach ($this->graph as $start => $data) {
Chris@0:       $this->depthFirstSearch($state, $start);
Chris@0:     }
Chris@0: 
Chris@0:     // We do such a numbering that every component starts with 0. This is useful
Chris@0:     // for module installs as we can install every 0 weighted module in one
Chris@0:     // request, and then every 1 weighted etc.
Chris@0:     $component_weights = [];
Chris@0: 
Chris@0:     foreach ($state['last_visit_order'] as $vertex) {
Chris@0:       $component = $this->graph[$vertex]['component'];
Chris@0:       if (!isset($component_weights[$component])) {
Chris@0:         $component_weights[$component] = 0;
Chris@0:       }
Chris@0:       $this->graph[$vertex]['weight'] = $component_weights[$component]--;
Chris@0:     }
Chris@0: 
Chris@0:     return $this->graph;
Chris@0:   }
Chris@0: 
Chris@0:   /**
Chris@0:    * Performs a depth-first search on a graph.
Chris@0:    *
Chris@0:    * @param $state
Chris@0:    *   An associative array. The key 'last_visit_order' stores a list of the
Chris@0:    *   vertices visited. The key components stores list of vertices belonging
Chris@0:    *   to the same the component.
Chris@0:    * @param $start
Chris@0:    *   An arbitrary vertex where we started traversing the graph.
Chris@0:    * @param $component
Chris@0:    *   The component of the last vertex.
Chris@0:    *
Chris@0:    * @see \Drupal\Component\Graph\Graph::searchAndSort()
Chris@0:    */
Chris@0:   protected function depthFirstSearch(&$state, $start, &$component = NULL) {
Chris@0:     // Assign new component for each new vertex, i.e. when not called recursively.
Chris@0:     if (!isset($component)) {
Chris@0:       $component = $start;
Chris@0:     }
Chris@0:     // Nothing to do, if we already visited this vertex.
Chris@0:     if (isset($this->graph[$start]['paths'])) {
Chris@0:       return;
Chris@0:     }
Chris@0:     // Mark $start as visited.
Chris@0:     $this->graph[$start]['paths'] = [];
Chris@0: 
Chris@0:     // Assign $start to the current component.
Chris@0:     $this->graph[$start]['component'] = $component;
Chris@0:     $state['components'][$component][] = $start;
Chris@0: 
Chris@0:     // Visit edges of $start.
Chris@0:     if (isset($this->graph[$start]['edges'])) {
Chris@0:       foreach ($this->graph[$start]['edges'] as $end => $v) {
Chris@0:         // Mark that $start can reach $end.
Chris@0:         $this->graph[$start]['paths'][$end] = $v;
Chris@0: 
Chris@0:         if (isset($this->graph[$end]['component']) && $component != $this->graph[$end]['component']) {
Chris@0:           // This vertex already has a component, use that from now on and
Chris@0:           // reassign all the previously explored vertices.
Chris@0:           $new_component = $this->graph[$end]['component'];
Chris@0:           foreach ($state['components'][$component] as $vertex) {
Chris@0:             $this->graph[$vertex]['component'] = $new_component;
Chris@0:             $state['components'][$new_component][] = $vertex;
Chris@0:           }
Chris@0:           unset($state['components'][$component]);
Chris@0:           $component = $new_component;
Chris@0:         }
Chris@0:         // Only visit existing vertices.
Chris@0:         if (isset($this->graph[$end])) {
Chris@0:           // Visit the connected vertex.
Chris@0:           $this->depthFirstSearch($state, $end, $component);
Chris@0: 
Chris@0:           // All vertices reachable by $end are also reachable by $start.
Chris@0:           $this->graph[$start]['paths'] += $this->graph[$end]['paths'];
Chris@0:         }
Chris@0:       }
Chris@0:     }
Chris@0: 
Chris@0:     // Now that any other subgraph has been explored, add $start to all reverse
Chris@0:     // paths.
Chris@0:     foreach ($this->graph[$start]['paths'] as $end => $v) {
Chris@0:       if (isset($this->graph[$end])) {
Chris@0:         $this->graph[$end]['reverse_paths'][$start] = $v;
Chris@0:       }
Chris@0:     }
Chris@0: 
Chris@0:     // Record the order of the last visit. This is the reverse of the
Chris@0:     // topological order if the graph is acyclic.
Chris@0:     $state['last_visit_order'][] = $start;
Chris@0:   }
Chris@0: 
Chris@0: }