Project

General

Profile

Paste
Download (4.71 KB) Statistics
| Branch: | Revision:

root / drupal7 / includes / graph.inc @ 6d8023f2

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
}