dfsearch

Depth-first graph search

collapse all in page

Syntax

Description

example

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.

example

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.

example

T = dfsearch(___,'Restart',true) restarts the search if no new nodes are reachable from the discovered nodes. You can use any of the input 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

collapse all

Open Script

Create and plot a graph.

s = [1 1 1 1 2 2 2 2 2 2 2 2 2 2 15 15 15 15 15];
t = [3 5 4 2 14 6 11 12 13 10 7 9 8 15 16 17 19 18 20];
G = graph(s,t);
plot(G)

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

v = dfsearch(G,17)

v =

    17
    15
     2
     1
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    16
    18
    19
    20
Open Script

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 = 

        Event         Node       Edge   
    ______________    ____    __________

    startnode           3     NaN    NaN
    discovernode        3     NaN    NaN
    edgetonew         NaN       3      4
    discovernode        4     NaN    NaN
    edgetonew         NaN       4      6
    discovernode        6     NaN    NaN
    finishnode          6     NaN    NaN
    finishnode          4     NaN    NaN
    edgetofinished    NaN       3      6
    edgetonew         NaN       3      7
    discovernode        7     NaN    NaN
    finishnode          7     NaN    NaN
    finishnode          3     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...

Open Script

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

         Event          Node       Edge   
    ________________    ____    __________

    startnode             4     NaN    NaN
    edgetonew           NaN       4      6
    startnode             1     NaN    NaN
    edgetonew           NaN       1      3
    edgetonew           NaN       3      2
    edgetonew           NaN       2      5
    edgetofinished      NaN       2      6
    edgetonew           NaN       2      7
    edgetodiscovered    NaN       7      2
    edgetofinished      NaN       1      4
    startnode             8     NaN    NaN
    edgetonew           NaN       8      9
    edgetonew           NaN       8     10
    edgetonew           NaN       8     11
    edgetonew           NaN       8     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'

edgenew = T.Edge(T.Event == 'edgetonew',:);
edgefin = T.Edge(T.Event == 'edgetofinished',:);
edgedis = T.Edge(T.Event == 'edgetodiscovered',:);

highlight(p,edgedis(:,1),edgedis(:,2),'EdgeColor','m')
highlight(p,edgenew(:,1),edgenew(:,2),'EdgeColor','g')
highlight(p,edgefin(:,1),edgefin(:,2),'EdgeColor','k')
highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')

Open Script

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 = dfsearch(g, 1, 'edgetodiscovered', 'Restart', true)

e =

     3     1
     6     4
     8     7

Reverse the direction of the 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 = rmedge(g, e(:, 1), e(:, 2));
gnew = addedge(gnew, e(:, 2), e(:, 1));
isdag(gnew)

ans =

  logical

   1


plot(gnew, 'Layout', 'force');

Related Examples

Input Arguments

collapse all

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

For more information, see graph or digraph.

Example: G = graph(1,2)

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

Starting node, specified as either a nonnegative scalar integer between 1 and numnodes(G), or a character vector containing a node name.

Example: dfsearch(G,1)

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.

  • 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 eventsDescriptionOutput
'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.

'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, and T.Edge:

  • 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'.

  • 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 | cell

Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside single quotes (' '). You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

Example: v = dfsearch(G,s,'Restart',true)

collapse all

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

collapse all

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

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.

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.

More About

collapse all

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:

function DFS(C)

  Event discovernode(C)
  
  FOR node N from successors of node C
    Event edgetonew(C,N), edgetodiscovered(C,N) or edgetofinished(C,N) depending on the state of node N
    IF event was edgetonew
      Call DFS(N)
    END
  END

  Event finish(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 FlagEvent 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.

See Also

| | |

Introduced in R2015b

Was this topic helpful?
MATLAB Documentation
Other Documentation
Support