% Test program for GrTheory functions
% Author: Sergiy Iglin
% e-mail: siglin@yandex.ru
% personal page: http://iglin.exponenta.ru
clear all
% select test:
% ntest=1 - grBase
% ntest=2 - grCoBase
% ntest=3 - grCoCycleBasis
% ntest=4 - grColEdge
% ntest=5 - grColVer
% ntest=6 - grComp
% ntest=7 - grCycleBasis
% ntest=8 - grDecOrd
% ntest=9 - grDistances
% ntest=10 - grEccentricity
% ntest=11 - grIsEulerian
% ntest=12 - grMaxComSu
% ntest=13 - grMaxFlows
% ntest=14 - grMaxMatch
% ntest=15 - grMaxStabSet
% ntest=16 - grMinAbsEdgeSet
% ntest=17 - grMinAbsVerSet
% ntest=18 - grMinCutSet
% ntest=19 - grMinEdgeCover
% ntest=20 - grMinSpanTree
% ntest=21 - grMinVerCover
% ntest=22 - grPERT
% ntest=23 - grPlot
% ntest=24 - grShortPath
% ntest=25 - grTravSale
ntest=23;
switch ntest % selected test
case 1, % grBase test
disp('The grBase test')
V=[0 4;4 4;0 0;4 0;8 4;8 0;12 4;12 0;...
-2 8;-4 4;0 -4;-4 -4;-4 0];
E=[1 2;3 4;2 4;2 5;4 6;5 6;5 7;6 8;8 7;...
1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11];
grPlot(V,E,'d','%d','');
title('\bfThe initial digraph')
BG=grBase(E);
disp('The bases of digraph:')
disp(' N vertexes')
for k1=1:size(BG,1),
fprintf('%2.0f ',k1)
fprintf('%d ',BG(k1,:))
fprintf('\n')
end
case 2, % grCoBase test
disp('The grCoBase test')
V=[0 4;4 4;0 0;4 0;8 4;8 0;12 4;12 0;...
-2 8;-4 4;0 -4;-4 -4;-4 0];
E=[2 1;3 4;2 4;2 5;4 6;5 6;5 7;6 8;8 7;...
1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11];
grPlot(V,E,'d','%d','');
title('\bfThe initial digraph')
CBG=grCoBase(E);
disp('The contrabasis of digraph:')
disp(' N vertexes')
for k1=1:size(CBG,1),
fprintf('%2.0f ',k1)
fprintf('%d ',CBG(k1,:))
fprintf('\n')
end
case 3, % grCoCycleBasis test
disp('The grCoCycleBasis test')
V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
3 0;3 -1;4 0]; % vertexes coordinates
E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;5 6;6 7;...
5 8;6 8;6 9;7 9;7 10;8 9;9 10;8 11;9 11;10 11]; % edges
E=[E [1:size(E,1)]']; % edges with numbers
grPlot(V,E,'g','','%d'); % the initial graph
title('\bfThe initial graph')
CoCycles=grCoCycleBasis(E); % all independences cut-sets
for k1=1:size(CoCycles,2),
grPlot(V,E(find(~CoCycles(:,k1)),:),'g','','%d'); % one cocycle
title(['\bfCocycle N' num2str(k1)]);
end
case 4, % grColEdge test
disp('The grColEdge test')
V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
3 0;3 -1;4 0]; % vertexes coordinates
E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;5 6;6 7;...
5 8;6 8;6 9;7 9;7 10;8 9;9 10;8 11;9 11;10 11]; % edges
grPlot(V,E,'g','','%d'); % the initial graph
title('\bfThe initial graph')
mCol=grColEdge(E); % the color problem for edges
fprintf('The colors of edges\n N edge N col\n');
fprintf(' %2.0f %2.0f\n',[1:length(mCol);mCol']);
grPlot(V,[E,mCol],'g','','%d'); % plot the colored graph
title('\bfThe graph with colored edges')
case 5, % grColVer test
disp('The grColVer test')
t=[0:4]';
V=[[5*sin(2*pi*t/5) 5*cos(2*pi*t/5)];...
[4*sin(2*pi*(t-0.5)/5) 4*cos(2*pi*(t-0.5)/5)];...
[2*sin(2*pi*(t-0.5)/5) 2*cos(2*pi*(t-0.5)/5)];[0 0]];
E=[1 7;7 2;2 8;8 3;3 9;9 4;4 10;10 5;5 6;6 1;...
1 10;2 6;3 7;4 8;5 9;1 12;2 13;3 14;4 15;5 11;...
6 14;7 15;8 11;9 12;10 13;...
11 12;12 13;13 14;14 15;15 11;1 16;2 16;3 16;4 16;5 16];
grPlot(V,E,'g','%d',''); % the initial graph
title('\bfThe initial graph')
nCol=grColVer(E); % the color problem for vertexes
fprintf('The colors of vertexes\n N ver N col\n');
fprintf(' %2.0f %2.0f\n',[1:length(nCol);nCol']);
grPlot([V,nCol],E,'g','%d',''); % plot the colored graph
title('\bfThe graph with colored vertexes')
case 6, % grComp test
disp('The grComp test')
V=[0 4;4 4;0 0;4 0;8 4;8 0;12 4;12 0;...
-2 8;-4 4;0 -4;-4 -4;-4 0];
E=[1 2;3 4;2 4;2 5;4 6;5 6;5 7;6 8;8 7;...
1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11];
ncV=grComp(E);
grPlot([V ncV],E,'g','%d','');
title(['\bfThis graph have ' num2str(max(ncV)) ' component(s)'])
E=[2 4;2 5;4 6;5 6;5 7;6 8;8 7;...
1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11];
ncV=grComp(E);
grPlot([V ncV],E,'g','%d','');
title(['\bfThis graph have ' num2str(max(ncV)) ' component(s)'])
E=[2 4;2 5;4 6;5 6;5 7;6 8;8 7;...
1 9;9 10;10 1;3 11;11 12;3 12];
ncV=grComp(E,size(V,1));
grPlot([V ncV],E,'g','%d','');
title(['\bfThis graph have ' num2str(max(ncV)) ' component(s)'])
case 7, % grCycleBasis test
disp('The grCycleBasis test')
V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
3 0;3 -1;4 0]; % vertexes coordinates
E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;5 6;6 7;...
5 8;6 8;6 9;7 9;7 10;8 9;9 10;8 11;9 11;10 11]; % edges
grPlot(V,E,'g','%d',''); % the initial graph
title('\bfThe initial graph')
Cycles=grCycleBasis(E); % all independences cycles
for k1=1:size(Cycles,2),
grPlot(V,E(find(Cycles(:,k1)),:),'g','%d',''); % one cycle
title(['\bfCycle N' num2str(k1)]);
end
case 8, % grDecOrd test
disp('The grDecOrd test')
V=[0 4;1 4;2 4;3 4;4 4;0 3;1 3;2 3;3 3;4 3;...
0 2;1 2;2 2;3 2;4 2;0 1;1 1;2 1;3 1;4 1;...
0 0;1 0;2 0;3 0;4 0];
E=[1 2;3 2;4 3;5 4;6 1;2 7;8 2;3 8;9 4;9 5;10 5;7 6;8 7;...
8 9;10 9;11 6;7 12;13 8;14 9;15 10;12 11;13 12;13 14;...
14 13;15 14;16 11;12 17;13 18;20 15;17 16;17 18;18 17;...
19 18;19 20;21 16;17 22;18 22;22 18;18 23;19 24;20 25;...
21 22;22 21;23 24;24 23;24 25];
grPlot(V,E,'d');
title('\bfThe initial digraph')
[Dec,Ord]=grDecOrd(E); % solution
disp('The classes of mutually connected vertexes:')
disp(' N vertexes')
for k1=1:size(Dec,2),
fprintf('%2.0f ',k1)
fprintf('%d ',find(Dec(:,k1)))
fprintf('\n')
end
fprintf('The partial ordering of the classes:\n ')
fprintf('%3.0f',1:size(Ord,2))
fprintf('\n')
for k1=1:size(Ord,1), % the matrix of partial ordering
fprintf('%2.0f ',k1)
fprintf(' %1.0f ',Ord(k1,:))
fprintf('\n')
end
V1=V;
for k1=1:size(Dec,2),
V1(find(Dec(:,k1)),3)=k1; % weight = number of the class
end
grPlot(V1,E,'d','%d','');
title('\bfThe classes of mutually connected vertexes')
case 9, % grDispances test
disp('The grDispances test')
V=[0 4;1 4;2 4;3 4;4 4;0 3;1 3;2 3;3 3;4 3;...
0 2;1 2;2 2;3 2;4 2;0 1;1 1;2 1;3 1;4 1;...
0 0;1 0;2 0;3 0;4 0];
E=[1 2 1;3 2 2;4 3 3;5 4 4;6 1 5;2 7 6;8 2 7;3 8 1;...
9 4 9;9 5 8;10 5 7;7 6 6;8 7 5;8 9 4;10 9 3;11 6 2;...
7 12 1;13 8 2;14 9 3;15 10 4;12 11 5;13 12 6;13 14 7;...
14 13 8;5 5 10;15 14 9;16 11 8;12 17 7;13 18 6;...
20 15 5;17 16 4;17 18 3;18 17 2;19 18 1;19 20 2;...
5 5 8; 21 16 3;17 22 4;18 22 5;22 18 6;18 23 7;...
19 24 8;20 25 9;21 22 8;22 21 7;23 24 6;10 10 8;...
24 23 5;24 25 4];
s=1; % one vertex
t=25; % other vertex
grPlot(V,E); % the initial graph
title('\bfThe initial graph with weighed edges')
[dSP,sp]=grDistances(E(:,1:2),s,t); % the nonweighted task
fprintf('The steps number between all vertexes:\n ')
fprintf('%4.0f',1:size(dSP,2))
fprintf('\n')
for k1=1:size(dSP,1), % the matrix of distances
fprintf('%3.0f ',k1)
fprintf(' %2.0f ',dSP(k1,:))
fprintf('\n')
end
grPlot(V(:,1:2),[sp(1:end-1);sp(2:end)]','d','%d','')
title(['\bfThe shortest way between vertex ' ...
num2str(s) ' and vertex ' num2str(t)])
[dSP,sp]=grDistances(E,1,25); % the weighted task
fprintf('The distances between all vertexes: