## root / drupal7 / includes / graph.inc @ 7dd8ec42

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