annotate core/lib/Drupal/Component/Graph/Graph.php @ 19:fa3358dc1485 tip

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