1 graph.inc | `backdrop_depth_first_search(&$graph)` |

Performs a depth-first search and sort on a directed acyclic graph.

### Parameters

**$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:

```
$graph[1]['edges'][2] = 1;
$graph[2]['edges'][3] = 1;
$graph[2]['edges'][4] = 1;
$graph[3]['edges'][4] = 1;
```

On return you will also have:

```
$graph[1]['paths'][2] = 1;
$graph[1]['paths'][3] = 1;
$graph[2]['reverse_paths'][1] = 1;
$graph[3]['reverse_paths'][1] = 1;
```

### Return value

** 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 also

_backdrop_depth_first_search()

### File

- core/
includes/ graph.inc, line 46 - Directed acyclic graph manipulation.

### Code

```
function backdrop_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) {
_backdrop_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]--;
}
}
```