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