MATLAB Examples

# Visualize Breadth-First and Depth-First Search

This example shows how to define a function that visualizes the results of bfsearch and dfsearch by highlighting the nodes and edges of a graph.

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

Perform a depth-first search on the graph. Specify 'allevents' to return all events in the algorithm. Also, specify Restart as true to ensure that the search visits every node in the graph.

```T = dfsearch(G, 1, 'allevents', 'Restart', true) ```
```T = 38x4 table Event Node Edge EdgeIndex ________________ ____ __________ _________ startnode 1 NaN NaN NaN discovernode 1 NaN NaN NaN edgetonew NaN 1 7 1 discovernode 7 NaN NaN NaN edgetonew NaN 7 3 10 discovernode 3 NaN NaN NaN edgetodiscovered NaN 3 1 3 edgetonew NaN 3 5 4 discovernode 5 NaN NaN NaN edgetonew NaN 5 4 8 discovernode 4 NaN NaN NaN edgetonew NaN 4 2 7 discovernode 2 NaN NaN NaN edgetonew NaN 2 6 2 discovernode 6 NaN NaN NaN edgetodiscovered NaN 6 4 9 finishnode 6 NaN NaN NaN finishnode 2 NaN NaN NaN finishnode 4 NaN NaN NaN finishnode 5 NaN NaN NaN edgetofinished NaN 3 6 5 edgetonew NaN 3 8 6 discovernode 8 NaN NaN NaN edgetodiscovered NaN 8 7 11 finishnode 8 NaN NaN NaN finishnode 3 NaN NaN NaN finishnode 7 NaN NaN NaN finishnode 1 NaN NaN NaN startnode 9 NaN NaN NaN discovernode 9 NaN NaN NaN edgetofinished NaN 9 1 12 edgetofinished NaN 9 6 13 edgetofinished NaN 9 8 14 finishnode 9 NaN NaN NaN startnode 10 NaN NaN NaN discovernode 10 NaN NaN NaN edgetofinished NaN 10 2 15 finishnode 10 NaN NaN NaN ```

The values in the table, T, are useful for visualizing the search. The function visualize_search.m shows one way to use the results of searches performed with bfsearch and dfsearch to highlight the nodes and edges in the graph according to the table of events, T. The function pauses before each step in the algorithm, so you can slowly step through the search by pressing any key.

Save visualize_search.m in the current folder.

```function visualize_search(G,t)
% G is a graph or digraph object, and t is a table resulting from a call to
% BFSEARCH or DFSEARCH on that graph.
%
% Example inputs:
% G = digraph([1 2 3 3 3 3 4 5 6 7 8 9 9 9 10], ...
%     [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2]);
% t = dfsearch(g, 1, 'allevents', 'Restart', true);

% Copyright 1984-2017 The MathWorks, Inc.

isundirected = isa(G, 'graph');
if isundirected
% Replace graph with corresponding digraph, because we need separate
% edges for both directions
[src, tgt] = findedge(G);
G = digraph([src; tgt], [tgt; src], [1:numedges(G), 1:numedges(G)]);
end

h = plot(G,'NodeColor',[0.5 0.5 0.5],'EdgeColor',[0.5 0.5 0.5], 'EdgeLabelMode', 'auto');

for ii=1:size(t,1)
switch t.Event(ii)
case 'startnode'
highlight(h,t.Node(ii),'MarkerSize',min(h.MarkerSize)*2);
case 'discovernode'
highlight(h,t.Node(ii),'NodeColor','r');
case 'finishnode'
highlight(h,t.Node(ii),'NodeColor','k');
otherwise
if isundirected
edgeind = intersect(find(G.Edges.Weight == t.EdgeIndex(ii)), ...
findedge(G, t.Edge(ii, 1), t.Edge(ii, 2)));
else
edgeind = t.EdgeIndex(ii);
end
switch t.Event(ii)
case 'edgetonew'
highlight(h,'Edges',edgeind,'EdgeColor','b');
case 'edgetodiscovered'
highlight(h,'Edges',edgeind,'EdgeColor',[0.8 0 0.8]);
case 'edgetofinished'
highlight(h,'Edges',edgeind,'EdgeColor',[0 0.8 0]);
end
end

nodeStr = t.Node;
if isnumeric(nodeStr)
nodeStr = num2cell(nodeStr);
nodeStr = cellfun(@num2str, nodeStr, 'UniformOutput', false);
end

edgeStr = t.Edge;
if isnumeric(edgeStr)
edgeStr = num2cell(edgeStr);
edgeStr = cellfun(@num2str, edgeStr, 'UniformOutput', false);
end

if ~isnan(t.Node(ii))
title([char(t{ii, 1}) ' on Node ' nodeStr{ii}]);
else
title([char(t{ii, 1}) ' on Edge (' edgeStr{ii, 1} ', ' edgeStr{ii, 2}, ...
') with edge index ' sprintf('%d ', t{ii, 4})]);
end

disp('Strike any key to continue...')
pause
end
disp('Done.')
close all

```

Use this command to run visualize_search.m on graph G and search result T:

`  visualize_search(G,T)`

The graph begins as all gray, and then a new piece of the search result appears each time you press a key. The search results are highlighted according to:

• 'startnode' - Starting nodes increase in size.
• 'discovernode' - Nodes turn red as they are discovered.
• 'finishnode' - Nodes turn black after they are finished.
• 'edgetonew' - Edges that lead to undiscovered nodes turn blue.
• 'edgetodiscovered' - Edges that lead to discovered nodes turn magenta.
• 'edgetofinished' - Edges that lead to finished nodes turn green.

This .gif animation shows what you see when you step through the results of visualize_search.m.