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