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