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