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