dfsearch

Depth-first graph search

Syntax

v = dfsearch(G,s)

T = dfsearch(G,s,events)

[T,E] = dfsearch(G,s,events)

[___] = dfsearch(___,'Restart',tf)

Description

v = dfsearch(G,s) applies depth-first search to graph G starting at node s. The result is a vector of node IDs in order of their discovery.

T = dfsearch(G,s,events) customizes the output of the depth-first search by flagging one or more search events. For example, T = dfsearch(G,s,'allevents') returns a table containing all flagged events, and X = dfsearch(G,s,'edgetonew') returns a matrix or cell array of edges.

[T,E] = dfsearch(G,s,events) additionally returns a vector of edge indices E when events is set to 'edgetonew', 'edgetodiscovered', or 'edgetofinished'. The edge indices are for unique identification of edges in a multigraph.

[___] = dfsearch(___,'Restart',tf), where tf is true, restarts the search if no new nodes are reachable from the discovered nodes. You can use any of the input or output argument combinations in previous syntaxes. This option ensures that the depth-first search reaches all nodes and edges in the graph, even if they are not reachable from the starting node, s.

Examples

Perform Depth-First Graph Search

Create and plot a graph.

s = [1 1 1 1 2 2 2 2 2];
t = [3 5 4 2 6 10 7 9 8];
G = graph(s,t);
plot(G)

Perform a depth-first search of the graph starting at node 7. The result indicates the order of node discovery.

v = dfsearch(G,7)

v = 10×1

     7
     2
     1
     3
     4
     5
     6
     8
     9
    10

Depth-First Graph Search with All Events

Create and plot a directed graph.

A = [0 1 0 1 1 0 0; 
     0 0 0 0 0 0 0; 
     0 0 0 1 0 1 1;
     0 0 0 0 0 1 0; 
     0 0 0 0 0 0 0; 
     0 0 0 0 0 0 0; 
     0 0 0 0 0 0 0];
G = digraph(A);
plot(G)

Perform a depth-first search on the graph starting at node 3. Specify 'allevents' to return a table containing all of the events in the algorithm.

T = dfsearch(G,3,'allevents')

T=13×4 table
        Event         Node       Edge       EdgeIndex
    ______________    ____    __________    _________

    startnode           3     NaN    NaN       NaN   
    discovernode        3     NaN    NaN       NaN   
    edgetonew         NaN       3      4         4   
    discovernode        4     NaN    NaN       NaN   
    edgetonew         NaN       4      6         7   
    discovernode        6     NaN    NaN       NaN   
    finishnode          6     NaN    NaN       NaN   
    finishnode          4     NaN    NaN       NaN   
    edgetofinished    NaN       3      6         5   
    edgetonew         NaN       3      7         6   
    discovernode        7     NaN    NaN       NaN   
    finishnode          7     NaN    NaN       NaN   
    finishnode          3     NaN    NaN       NaN   

To follow the steps in the algorithm, read the events in the table from top to bottom. For example:

1. The algorithm begins at node 3

2. An edge is discovered between node 3 and node 4

3. Node 4 is discovered

4. and so on...

Depth-First Graph Search with Multiple Components

Perform a depth-first search of a graph with multiple components, and then highlight the graph nodes and edges based on the search results.

Create and plot a directed graph. This graph has two weakly connected components.

s = [1 1 2 2 2 3 4 7 8 8 8 8];
t = [3 4 7 5 6 2 6 2 9 10 11 12];
G = digraph(s,t);
p = plot(G,'Layout','layered');

c = conncomp(G,'Type','weak')

c = 1×12

     1     1     1     1     1     1     1     2     2     2     2     2

Perform a depth-first search of the graph starting at node 4, and flag the 'edgetonew', 'edgetodiscovered', 'edgetofinished', and 'startnode' events. Specify Restart as true to make the search restart whenever there are remaining nodes that cannot be reached.

events = {'edgetonew','edgetodiscovered','edgetofinished','startnode'};
T = dfsearch(G,4,events,'Restart',true)

T=15×4 table
         Event          Node       Edge       EdgeIndex
    ________________    ____    __________    _________

    startnode             4     NaN    NaN       NaN   
    edgetonew           NaN       4      6         7   
    startnode             1     NaN    NaN       NaN   
    edgetonew           NaN       1      3         1   
    edgetonew           NaN       3      2         6   
    edgetonew           NaN       2      5         3   
    edgetofinished      NaN       2      6         4   
    edgetonew           NaN       2      7         5   
    edgetodiscovered    NaN       7      2         8   
    edgetofinished      NaN       1      4         2   
    startnode             8     NaN    NaN       NaN   
    edgetonew           NaN       8      9         9   
    edgetonew           NaN       8     10        10   
    edgetonew           NaN       8     11        11   
    edgetonew           NaN       8     12        12   

When Restart is true, the 'startnode' event returns information about where and when the algorithm restarts the search.

Highlight the graph based on event:

• Color the starting nodes red.

• Green edges are for 'edgetonew'

• Black edges are for 'edgetofinished'

• Magenta edges are for 'edgetodiscovered'

highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'g')
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetofinished'), 'EdgeColor', 'k') 
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetodiscovered'), 'EdgeColor', 'm') 
highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')

Remove Cycles from Graph

Make a directed graph acyclic by reversing some of its edges.

Create and plot a directed graph.

s = [1 2 3 3 3 3 4 5 6 7 8 9 9 9 10];
t = [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2];
g = digraph(s,t);
plot(g, 'Layout', 'force')

Perform a depth-first search on the graph, flagging the 'edgetodiscovered' event. This event corresponds to edges that complete a cycle.

[e,edge_indices] = dfsearch(g, 1, 'edgetodiscovered', 'Restart', true)

e = 3×2

     3     1
     6     4
     8     7

edge_indices = 3×1

     3
     9
    11

Use flipedge to reverse the direction of the flagged edges, so that they no longer complete a cycle. This removes all cycles from the graph. Use isdag to confirm that the graph is acyclic.

gnew = flipedge(g, edge_indices);
isdag(gnew)

ans = logical
   1

Plot the new graph and highlight the edges that were flipped.

p = plot(gnew, 'Layout', 'force');
highlight(p,'Edges',findedge(gnew,e(:,2),e(:,1)),'EdgeColor','r')

Input Arguments

G — Input graph

graph object | digraph object

Input graph, specified as either a graph or digraph object. Use graph to create an undirected graph or digraph to create a directed graph.

Example: G = graph(1,2)

Example: G = digraph([1 2],[2 3])

s — Starting node

node index | node name

Starting node, specified as one of the values in this table.

Value	Example
Scalar node index	1
Character vector node name	'A'
String scalar node name	"A"

Example: dfsearch(G,1)

events — Flagged search events

'discovernode' (default) | 'startnode' | 'finishnode' | 'edgetonew' | 'edgetodiscovered' | 'edgetofinished' | 'allevents' | cell array | string array

Flagged search events, specified as one of the options in the following table.

• To flag single events, use the flag names.

• To flag a subset of events, put two or more flag names into a cell array or string array.

• To flag all events, use 'allevents'.

Note

Depending on the value of events, the output of dfsearch varies. See the last column in the following table for information about the output returned by each option.

Value of events	Description	Output
'discovernode' (default)	A new node has been discovered.	Return a vector of node IDs: If s is a numeric node index, then the vector contains numeric node indices. If s is a node name, then the vector is a cell array containing node names.
'finishnode'	All outgoing edges from the node have been visited.
'startnode'	This flag indicates the starting node in the search. If 'Restart' is true, then 'startnode' flags the starting node each time the search restarts.
'edgetonew'	Edge connects to an undiscovered node.	Return a matrix or cell array of size N-by-2 that specifies the end nodes of edges in the graph: If s is a numeric node index, then the matrix contains numeric node indices. If s is a node name, then the matrix is a cell array containing node names. Additionally, you can specify a second output with [T,E] = dfsearch(…) that returns a vector of edge indices E.
'edgetodiscovered'	Edge connects to a previously discovered node.
'edgetofinished'	Edge connects to a finished node.
cell array	Specify two or more flags in a cell array to only flag those events during the search.	Return a table, T, which contains the variables T.Event, T.Node, T.Edge, and T.EdgeIndex: T.Event is a categorical vector containing the flags in order of their occurrence. T.Node contains the node ID of the corresponding node for the events 'discovernode', 'finishnode', and 'startnode'. T.Edge contains the corresponding edge for the events 'edgetonew', 'edgetodiscovered', and 'edgetofinished'. T.EdgeIndex contains the edge index for the events 'edgetonew', 'edgetodiscovered', and 'edgetofinished'. The edge index is for unique identification of repeated edges in a multigraph. Unused elements of T.Node and T.Edge are set to NaN. If s is a numeric node index, then T.Node and T.Edge contain numeric node indices. If s is a node name, then T.Node and T.Edge are cell arrays containing node names.
'allevents'	All events are flagged.

Example: v = dfsearch(G,3) begins the search at the third node and returns a vector, v, containing the nodes in order of discovery. This is the same as v = dfsearch(G,3,'discovernode').

Example: X = dfsearch(G,'A','edgetonew') begins at the node named 'A' and returns a cell array of character vectors, X, indicating each of the edges that connects to an undiscovered node during the search.

Example: T = dfsearch(G,s,{'discovernode','finishnode'}) returns a table, T, but only flags when new nodes are discovered or when a node is marked finished.

Example: T = dfsearch(G,s,'allevents') flags all search events and returns a table, T.

Data Types: char | string | cell

tf — Toggle to restart search

false (default) | true

Toggle to restart search, specified as false (default) or true. This option is useful if the graph contains nodes that are unreachable from the starting node. If 'Restart' is true, then the search restarts whenever undiscovered nodes remain that are unreachable from the discovered nodes. The new start node is the node with smallest index that is still undiscovered. The restarting process repeats until dfsearch discovers all nodes.

'Restart' is false by default, so that the search only visits nodes that are reachable from the starting node.

When 'Restart' is true, the 'discovernode' and 'finishnode' events occur once for each node in the graph. Also, each edge in the graph is flagged once by 'edgetonew', 'edgetodiscovered', or 'edgetofinished'. The edges flagged by 'edgetonew' form one or more trees.

Example: T = dfsearch(graph([1 3],[2 4]),1,'Restart',true) searches both of the connected components in the graph.

Data Types: logical

Output Arguments

v — Node IDs

numeric column vector | cell vector

Node IDs, returned in one of the following formats:

• If you use a numeric node ID to specify the starting node, s, then v is a numeric column vector of node indices.

• If s is a character vector or string containing a node name, then v is a cell vector containing node names.

The node IDs in v reflect the order of discovery by the depth-first graph search.

T — Search results

table | vector | matrix | cell array of node names

Search results, returned in one of the following formats:

• If events is not specified or is 'discovernode', 'finishnode', or 'startnode', then T is a vector of node IDs similar to v.

• If events is 'edgetonew', 'edgetodiscovered', or 'edgetofinished', then T is a matrix or cell array of size N-by-2 indicating the source and target nodes for each relevant edge.

• If events is a cell array of search events or 'allevents', then T is a table containing the flagged search events. The table contains the search event flags in T.Event, relevant node IDs in T.Node, and relevant edges in T.Edge and T.EdgeIndex.

In all cases:

• The order of the elements or rows of T indicates their order of occurrence during the search.

• If you specify s as a numeric node ID, then T also refers to nodes using their numeric IDs.

• If you specify s as a node name, then T also refers to nodes using their names.

E — Edge indices

vector

Edge indices, returned as a vector.

Specify this output to get a vector of edge indices for the events 'edgetonew', 'edgetodiscovered', or 'edgetofinished'. The N-by-1 vector of edge indices corresponds with T, which is a matrix or cell array of size N-by-2 indicating the source and target nodes for each relevant edge.

Example: [T,E] = dfsearch(G,s,'edgetonew')

Tips

• dfsearch and bfsearch treat undirected graphs the same as directed graphs. An undirected edge between nodes s and t is treated like two directed edges, one from s to t and one from t to s.

Algorithms

The Depth-First search algorithm begins at the starting node, s, and inspects the neighbor of s that has the smallest node index. Then for that neighbor, it inspects the next undiscovered neighbor with the lowest index. This continues until the search encounters a node whose neighbors have all been visited. At that point, the search backtracks along the path to the nearest previously discovered node that has an undiscovered neighbor. This process continues until all nodes that are reachable from the starting node have been visited.

In pseudo-code, the (recursive) algorithm can be written as:

Event startnode(S)
Call DFS(S)

function DFS(C)

  Event discovernode(C)
  
  FOR edge E from outgoing edges of node C, connecting to node N
    Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E) 
    (depending on the state of node N)
    IF event was edgetonew
      Call DFS(N)
    END
  END

Event finishnode(C)  

END

dfsearch can return flags to describe the different events in the algorithm, such as when a new node is discovered or when all of the outgoing edges of a node have been visited. The event flags are listed here.

Event Flag	Event Description
'discovernode'	A new node has been discovered.
'finishnode'	All outgoing edges from the node have been visited.
'startnode'	This flag indicates the starting node in the search.
'edgetonew'	Edge connects to an undiscovered node
'edgetodiscovered'	Edge connects to a previously discovered node
'edgetofinished'	Edge connects to a finished node

For more information, see the input argument description for events.

Note

In cases where the input graph contains nodes that are unreachable from the starting node, the 'Restart' option provides a way to make the search visit every node in the graph. In that case, the 'startnode' event indicates the starting node each time the search restarts.

Extended Capabilities

Thread-Based Environment
Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

Version History

Introduced in R2015b