aleph1.co.uk Git - yaffs-website/blob - web/core/lib/Drupal/Component/Graph/Graph.php

   1 <?php
   2
   3 namespace Drupal\Component\Graph;
   4
   5 /**
   6  * Directed acyclic graph manipulation.
   7  */
   8 class Graph {
   9
  10   /**
  11    * Holds the directed acyclic graph.
  12    */
  13   protected $graph;
  14
  15   /**
  16    * Instantiates the depth first search object.
  17    *
  18    * @param $graph
  19    *   A three dimensional associated array, with the first keys being the names
  20    *   of the vertices, these can be strings or numbers. The second key is
  21    *   'edges' and the third one are again vertices, each such key representing
  22    *   an edge. Values of array elements are copied over.
  23    *
  24    *   Example:
  25    *   @code
  26    *     $graph[1]['edges'][2] = 1;
  27    *     $graph[2]['edges'][3] = 1;
  28    *     $graph[2]['edges'][4] = 1;
  29    *     $graph[3]['edges'][4] = 1;
  30    *   @endcode
  31    *
  32    *   On return you will also have:
  33    *   @code
  34    *     $graph[1]['paths'][2] = 1;
  35    *     $graph[1]['paths'][3] = 1;
  36    *     $graph[2]['reverse_paths'][1] = 1;
  37    *     $graph[3]['reverse_paths'][1] = 1;
  38    *   @endcode
  39    */
  40   public function __construct($graph) {
  41     $this->graph = $graph;
  42   }
  43
  44   /**
  45    * Performs a depth-first search and sort on the directed acyclic graph.
  46    *
  47    * @return
  48    *   The given $graph with more secondary keys filled in:
  49    *   - 'paths': Contains a list of vertices than can be reached on a path from
  50    *     this vertex.
  51    *   - 'reverse_paths': Contains a list of vertices that has a path from them
  52    *     to this vertex.
  53    *   - 'weight': If there is a path from a vertex to another then the weight of
  54    *     the latter is higher.
  55    *   - 'component': Vertices in the same component have the same component
  56    *     identifier.
  57    */
  58   public function searchAndSort() {
  59     $state = [
  60       // The order of last visit of the depth first search. This is the reverse
  61       // of the topological order if the graph is acyclic.
  62       'last_visit_order' => [],
  63       // The components of the graph.
  64       'components' => [],
  65     ];
  66     // Perform the actual search.
  67     foreach ($this->graph as $start => $data) {
  68       $this->depthFirstSearch($state, $start);
  69     }
  70
  71     // We do such a numbering that every component starts with 0. This is useful
  72     // for module installs as we can install every 0 weighted module in one
  73     // request, and then every 1 weighted etc.
  74     $component_weights = [];
  75
  76     foreach ($state['last_visit_order'] as $vertex) {
  77       $component = $this->graph[$vertex]['component'];
  78       if (!isset($component_weights[$component])) {
  79         $component_weights[$component] = 0;
  80       }
  81       $this->graph[$vertex]['weight'] = $component_weights[$component]--;
  82     }
  83
  84     return $this->graph;
  85   }
  86
  87   /**
  88    * Performs a depth-first search on a graph.
  89    *
  90    * @param $state
  91    *   An associative array. The key 'last_visit_order' stores a list of the
  92    *   vertices visited. The key components stores list of vertices belonging
  93    *   to the same the component.
  94    * @param $start
  95    *   An arbitrary vertex where we started traversing the graph.
  96    * @param $component
  97    *   The component of the last vertex.
  98    *
  99    * @see \Drupal\Component\Graph\Graph::searchAndSort()
 100    */
 101   protected function depthFirstSearch(&$state, $start, &$component = NULL) {
 102     // Assign new component for each new vertex, i.e. when not called recursively.
 103     if (!isset($component)) {
 104       $component = $start;
 105     }
 106     // Nothing to do, if we already visited this vertex.
 107     if (isset($this->graph[$start]['paths'])) {
 108       return;
 109     }
 110     // Mark $start as visited.
 111     $this->graph[$start]['paths'] = [];
 112
 113     // Assign $start to the current component.
 114     $this->graph[$start]['component'] = $component;
 115     $state['components'][$component][] = $start;
 116
 117     // Visit edges of $start.
 118     if (isset($this->graph[$start]['edges'])) {
 119       foreach ($this->graph[$start]['edges'] as $end => $v) {
 120         // Mark that $start can reach $end.
 121         $this->graph[$start]['paths'][$end] = $v;
 122
 123         if (isset($this->graph[$end]['component']) && $component != $this->graph[$end]['component']) {
 124           // This vertex already has a component, use that from now on and
 125           // reassign all the previously explored vertices.
 126           $new_component = $this->graph[$end]['component'];
 127           foreach ($state['components'][$component] as $vertex) {
 128             $this->graph[$vertex]['component'] = $new_component;
 129             $state['components'][$new_component][] = $vertex;
 130           }
 131           unset($state['components'][$component]);
 132           $component = $new_component;
 133         }
 134         // Only visit existing vertices.
 135         if (isset($this->graph[$end])) {
 136           // Visit the connected vertex.
 137           $this->depthFirstSearch($state, $end, $component);
 138
 139           // All vertices reachable by $end are also reachable by $start.
 140           $this->graph[$start]['paths'] += $this->graph[$end]['paths'];
 141         }
 142       }
 143     }
 144
 145     // Now that any other subgraph has been explored, add $start to all reverse
 146     // paths.
 147     foreach ($this->graph[$start]['paths'] as $end => $v) {
 148       if (isset($this->graph[$end])) {
 149         $this->graph[$end]['reverse_paths'][$start] = $v;
 150       }
 151     }
 152
 153     // Record the order of the last visit. This is the reverse of the
 154     // topological order if the graph is acyclic.
 155     $state['last_visit_order'][] = $start;
 156   }
 157
 158 }