summaryrefslogtreecommitdiff
path: root/kolab.org/www/drupal-7.26/includes/graph.inc
diff options
context:
space:
mode:
Diffstat (limited to 'kolab.org/www/drupal-7.26/includes/graph.inc')
-rw-r--r--kolab.org/www/drupal-7.26/includes/graph.inc145
1 files changed, 145 insertions, 0 deletions
diff --git a/kolab.org/www/drupal-7.26/includes/graph.inc b/kolab.org/www/drupal-7.26/includes/graph.inc
new file mode 100644
index 0000000..35e6830
--- /dev/null
+++ b/kolab.org/www/drupal-7.26/includes/graph.inc
@@ -0,0 +1,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;
+}