%      Search.M
%   
%  Graph search methods
%  
% J. Lunze
% 
% 5.1.2023
% Version v. 11.4.2023
%
echo off
clear
close all

%%   Demonstrate Dijkstra's algorithm
%
figure(1)
%  Weighted graph of Section 3.3.4
N1=12;
AG=[0 2 1 0 0 0 0 0 0 0 0 0;
    2 0 3 1 0 0 6 0 0 0 0 0
    1 3 0 0 4 6 0 0 0 0 0 0
    0 1 0 0 1 0 6 0 0 0 0 0
    0 0 4 1 0 1 0 4 2 0 0 0
    0 0 6 0 1 0 0 0 0 0 0 3
    0 6 0 6 0 0 0 1 0 1 0 0
    0 0 0 0 4 0 1 0 1 2 4 0
    0 0 0 0 2 0 0 1 0 0 2 0
    0 0 0 0 0 0 1 2 0 0 1 0
    0 0 0 0 0 0 0 4 2 1 0 2
    0 0 0 0 0 3 0 0 0 0 2 0];
X=[1 2 2 3 3 3 4 4 4 5 5 4];  
Y=[4 5 3 4 2 1 6 4 2 5 3 1];
G=graph(AG);
h=plot(G,'XData',X,'YData',Y, 'EdgeLabel',G.Edges.Weight,...
    'EdgeFontSize', 12,'EdgeFontAngle','normal','NodeFontSize',14,...
    'MarkerSize',7,'LineWidth',1.8);
xleer;
yleer;
%  Shortest path with Dijkstra's algorithm
[Path,d]=shortestpath(G, 1, 8, 'Method','positive');
highlight(h,Path,'EdgeColor','r','NodeColor','r','LineWidth',5.0, 'MarkerSize',10,...
    'NodeFontSize', 14,'EdgeFontSize', 14);


%%   Depth-first search vs. breadth-first search
%
figure(2)
%
%  Undirected graph of Section 3.3
s=[7 4 2 1 1 3 2 5 6 5];
t=[8 5 5 2 7 4 3 7 7 6];
X=[1 2 3 4 3 3 2 1];
Y=[3 4 5 4 3 1 2 1];
G=graph(s,t);
h=plot(G,'XData',X,'YData',Y,'LineWidth',1.8);
%
%  Depth-first search
%events = {'edgetonew','edgetodiscovered','edgetofinished'};
events={'discovernode','edgetonew'};
T = dfsearch(G,1,events);
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',5, 'MarkerSize',10,'NodeFontSize', 14);
xleer;
yleer;
%
%  Breadth-first search
figure(3)
h=plot(G,'XData',X,'YData',Y,'LineWidth',1.8);
T = bfsearch(G,1,'allevents');
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',5, 'MarkerSize',10,'NodeFontSize', 14);
xleer;
yleer;

%%  Find the condensation of a graph
%
figure(4)
subplot(3,1,[1,2]);
%  Graph of Section 3.2.4
s=[1 2 2 2 3 4 5];
t=[2 3 5 6 4 3 1];
X=[1 3 4 5 2 4];
Y=[2 2 2 2 1 1];
G=digraph(s,t);
h=plot(G,'XData',X,'YData',Y,'LineWidth',1.5,'MarkerSize',9,...
    'NodeFontSize', 14,'LineWidth',1.8);
xleer;
yleer;
%
subplot(3,1,3)
Gred=condensation(G);
Xred=[1 2 3];
Yred=[1 1 1];
h=plot(Gred,'XData',Xred,'YData',Yred,'LineWidth',1.5,'MarkerSize',9,...
    'NodeFontSize', 14,'LineWidth',1.8);
xleer;
yleer;


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Graph search in lattice graphs
%
figure(5)
%  Lattice graph with N1 rows and columns
%  Vertices: 1, 2,..., N1^2
N1=6;
s=[];  
t=[];   % vectors of end vertices of the edges
X=[];
Y=[];
k3=0;   % index of the edge
%  coordinates of the vertices
for k2=0:N1-1
    for k1=1:N1
        k3=k3+1;
        X(k3)=k1;
        Y(k3)=k2;
    end
end
k4=0;
%  horizontal edges
for k2=0:N1-1
    for k1=1:N1-1
        k4=k4+1;      % next edge
        s(k4)=N1*k2+k1; % start vertex
        t(k4)=s(k4)+1; % end vertex
    end
end
%  vertical edges
for k1=1:N1
    for k2=0:N1-2
        k4=k4+1;      % next edge
        s(k4)=N1*k2+k1; % start node
        t(k4)=s(k4)+N1;
    end
end
G=graph(s,t);
h=plot(G, 'XData',X, 'YData',Y, 'LineWidth',1.8,  'MarkerSize',7,'NodeFontSize', 14);
xleer;
yleer;
latextitle('$${\tt Search:}$$ Lattice');


%%  Comparison of depth-first search and breadth-first search
%
figure(6)
%
A=1;         % root vertex
%  Depth-first search
h=plot(G, 'XData',X, 'YData',Y,'LineWidth',1.8);
events={'discovernode','edgetonew'};
T = dfsearch(G,A,events);
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',5, 'MarkerSize',10,'NodeFontSize', 14);
highlight(h,A);
xleer;
yleer;
latextitle('$${\tt Search:}$$ Depth-first search');
%
%  Breadth-first search
figure(7)
h=plot(G, 'XData',X, 'YData',Y,'LineWidth',1.8);
events={'discovernode','edgetonew'};
T = bfsearch(G,A,events);
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',5, 'MarkerSize',10,'NodeFontSize', 14);
highlight(h,A);
xleer;
yleer;
hold on
%   Visualisation of the distance from the root vertex
for d=1:6
    xmin=0.5;
    xmax=1+(d-1)+0.5;
    ymax=(d-1)+0.5;
    ymin=-0.5;
    plot([xmin xmax],[ymax, ymin],'b--');
    latextext(xmax+0.1, ymin, num2str(d,1));
end
for d=7:11
    xmin=max(0.5, (d-N1)+0.5);
    xmax=min(6.5, 1+(d-1)+0.5);
    ymax=min((d-1)+0.5, N1-0.5);
    ymin=-0.5+(d-6);
    plot([xmin xmax],[ymax, ymin],'b--');
end
latextext(0.3, -0.5, '$$d=$$');
axis([0 N1+1 -1 N1]);
latextitle('$${\tt Search:}$$ Breadth-first search');
hold off




%%  Comparison of depth-first search and breadth-first search
%
figure(8)
%
A=22;
B=4;
%  Depth-first search
h=plot(G, 'XData',X, 'YData',Y,'LineWidth',1.6);
events={'discovernode','edgetonew'};
T = dfsearch(G,A,events);
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',5, 'MarkerSize',10,'NodeFontSize', 14);
highlight(h,A, 'MarkerSize',12);
highlight(h,B, 'MarkerSize',12);
latextitle('$${\tt Search:}$$ Depth-first search');
hold off
xleer;
yleer;
%
%  Breadth-first search
figure(9)
h=plot(G, 'XData',X, 'YData',Y,'LineWidth',1.6);
events={'discovernode','edgetonew'};
T = bfsearch(G,A,events);
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',5, 'MarkerSize',10,'NodeFontSize', 14);
highlight(h,A, 'MarkerSize',12);
highlight(h,B, 'MarkerSize',12);
xleer;
yleer;
hold on
plot([4 1.5 4 6.5 4],[5.5 3 0.5 3 5.5],'b--');
latextitle('$${\tt Search:}$$ Breadth-first search');
hold off


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Comparison of depth-first search and breadth-first search
%   for a large random graph
%
figure(10)
p=0.25;
N1=25;
AG=ceil(rand(N1,N1)-(1-p)*ones(N1,N1));
G=digraph(AG);
A=1;
%  Depth-first search
subplot(1,2,1)
h=plot(G,'LineWidth',1.8);
events={'discovernode','edgetonew'};
T = dfsearch(G,A,events);
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',2.4, 'MarkerSize',7,'NodeFontSize', 14);
highlight(h,A,'MarkerSize',12);
latextitle('$${\tt Search:}$$ Depth-first search');
xleer;
yleer;
hold off
%  Breadth-first search
subplot(1,2,2)
h=plot(G,'LineWidth',1.8);
events={'discovernode','edgetonew'};
T = bfsearch(G,A,events);
highlight(h, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'r',...
    'LineWidth',2.4, 'MarkerSize',7,'NodeFontSize', 14);
highlight(h,A, 'MarkerSize',12);
xleer;
yleer;
latextitle('Breadth-first search');
hold off;



%%
%   EPS-figure
%
epsfigc12('Search');






