graph.inc 4.7 KB

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