Этот пример показывает, как задать функцию, которая визуализирует результаты bfsearch и dfsearch путем выделения узлов и ребер графика.
Создайте и постройте ориентированного графа.
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)
Выполните поиск в глубину на графике. Задайте 'allevents', чтобы возвратить все события в алгоритме. Кроме того, задайте Restart как true, чтобы гарантировать, что поиск посещает каждый узел в графике.
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
Значения в таблице, T, полезны для визуализации поиска. Функциональный visualize_search.m показывает один способ использовать результаты поисковых запросов, выполняемых с bfsearch и dfsearch, чтобы подсветить узлы и ребра в графике согласно таблице событий, T. Функция делает паузу перед каждым шагом в алгоритме, таким образом, можно медленно продвигаться посредством поиска путем нажатия любой клавиши.
Сохраните visualize_search.m в текущей папке.
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
Используйте эту команду, чтобы запустить visualize_search.m на графике G и результат поиска T:
visualize_search(G,T)
График начинается как полностью серый, и затем новая часть результата поиска появляется каждый раз, когда вы нажимаете клавишу. Результаты поиска подсвечены согласно:
'startnode' - Стартовые узлы увеличиваются в размере.
'discovernode' - Узлы покраснели, когда они обнаружены.
'finishnode' - Узлы становятся черными после того, как они будут закончены.
'edgetonew' - Ребра, которые приводят к неоткрытым узлам, становятся синими.
'edgetodiscovered' - Ребра, которые приводят к обнаруженным узлам, меняют цвет на пурпурный.
'edgetofinished' - Ребра, которые приводят к законченным узлам, становятся зелеными.
Эта анимация .gif показывает то, что вы видите, когда вы продвигаетесь через результаты visualize_search.m.
bfsearch | dfsearch | digraph | graph