%% 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')

%
% 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)

%
% 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')

% Copyright 2015 The MathWorks, Inc.