# graphtraverse

Traverse graph by following adjacent nodes

## Syntax

```[disc, pred, closed] = graphtraverse(G, S) [...] = graphtraverse(G, S, ...'Depth', DepthValue, ...) [...] = graphtraverse(G, S, ...'Directed', DirectedValue, ...) [...] = graphtraverse(G, S, ...'Method', MethodValue, ...) ```

## Arguments

 `G` N-by-N sparse matrix that represents a directed graph. Nonzero entries in matrix `G` indicate the presence of an edge. `S` Integer that indicates the source node in graph `G`. `DepthValue` Integer that indicates a node in graph `G` that specifies the depth of the search. Default is `Inf` (infinity). `DirectedValue` Property that indicates whether graph `G` is directed or undirected. Enter `false` for an undirected graph. This results in the upper triangle of the sparse matrix being ignored. Default is `true`. `MethodValue` Character vector or string that specifies the algorithm used to traverse the graph. Choices are:`'BFS'` — Breadth-first search. Time complexity is `O(N+E)`, where `N` and `E` are number of nodes and edges respectively.`'DFS'` — Default algorithm. Depth-first search. Time complexity is `O(N+E)`, where `N` and `E` are number of nodes and edges respectively.

## Description

Tip

For introductory information on graph theory functions, see Graph Theory Functions.

`[disc, pred, closed] = graphtraverse(G, S)` traverses graph `G` starting from the node indicated by integer `S`. `G` is an N-by-N sparse matrix that represents a directed graph. Nonzero entries in matrix `G` indicate the presence of an edge. `disc` is a vector of node indices in the order in which they are discovered. `pred` is a vector of predecessor node indices (listed in the order of the node indices) of the resulting spanning tree. `closed` is a vector of node indices in the order in which they are closed.

`[...] = graphtraverse(G, S, ...'PropertyName', PropertyValue, ...)` calls `graphtraverse` with optional properties that use property name/property value pairs. You can specify one or more properties in any order. Each `PropertyName` must be enclosed in single quotes and is case insensitive. These property name/property value pairs are as follows:

``` [...] = graphtraverse(G, S, ...'Depth', DepthValue, ...)``` specifies the depth of the search. `DepthValue` is an integer indicating a node in graph `G`. Default is `Inf` (infinity).

`[...] = graphtraverse(G, S, ...'Directed', DirectedValue, ...)` indicates whether the graph is directed or undirected. Set `DirectedValue` to `false` for an undirected graph. This results in the upper triangle of the sparse matrix being ignored. Default is `true`.

`[...] = graphtraverse(G, S, ...'Method', MethodValue, ...)` lets you specify the algorithm used to traverse the graph. Choices are:

• `'BFS'` — Breadth-first search. Time complexity is `O(N+E)`, where `N` and `E` are number of nodes and edges respectively.

• `'DFS'` — Default algorithm. Depth-first search. Time complexity is `O(N+E)`, where `N` and `E` are number of nodes and edges respectively.

## Examples

1. Create a directed graph with 10 nodes and 12 edges.

```DG = sparse([1 2 3 4 5 5 5 6 7 8 8 9],... [2 4 1 5 3 6 7 9 8 1 10 2],true,10,10) DG = (3,1) 1 (8,1) 1 (1,2) 1 (9,2) 1 (5,3) 1 (2,4) 1 (4,5) 1 (5,6) 1 (5,7) 1 (7,8) 1 (6,9) 1 (8,10) 1 h = view(biograph(DG)) Biograph object with 10 nodes and 12 edges.``` 2. Traverse the graph to find the depth-first search (DFS) discovery order starting at node 4.

```order = graphtraverse(DG,4) order = 4 5 3 1 2 6 9 7 8 10 ```
3. Label the nodes with the DFS discovery order.

```for i = 1:10 h.Nodes(order(i)).Label =... sprintf('%s:%d',h.Nodes(order(i)).ID,i); end h.ShowTextInNodes = 'label' dolayout(h)``` 4. Traverse the graph to find the breadth-first search (BFS) discovery order starting at node 4.

```order = graphtraverse(DG,4,'Method','BFS') order = 4 5 3 6 7 1 9 8 2 10 ```
5. Label the nodes with the BFS discovery order.

```for i = 1:10 h.Nodes(order(i)).Label =... sprintf('%s:%d',h.Nodes(order(i)).ID,i); end h.ShowTextInNodes = 'label' dolayout(h)``` 6. Find and color nodes that are close to (within two edges of) node 4.

```node_idxs = graphtraverse(DG,4,'depth',2) node_idxs = 4 5 3 6 7 set(h.nodes(node_idxs),'Color',[1 0 0])``` ## References

 Sedgewick, R., (2002). Algorithms in C++, Part 5 Graph Algorithms (Addison-Wesley).

 Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

Introduced in R2006b

## Support Get trial now