% Test program for GrTheory functions
% Author: Sergii 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 - grIsomorph
% ntest=13 - grMaxComSu
% ntest=14 - grMaxFlows
% ntest=15 - grMaxMatch
% ntest=16 - grMaxStabSet
% ntest=17 - grMinAbsEdgeSet
% ntest=18 - grMinAbsVerSet
% ntest=19 - grMinCutSet
% ntest=20 - grMinEdgeCover
% ntest=21 - grMinSpanTree
% ntest=22 - grMinVerCover
% ntest=23 - grPERT
% ntest=24 - grPlot
% ntest=25 - grShortPath
% ntest=26 - grShortVerPath
% ntest=27 - grTranClos
% ntest=28 - grTravSale
ntest=26;
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:\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 way with minimal weight between vertex ' ...
num2str(s) ' and vertex ' num2str(t)])
case 10, % grEccentricity test
disp('The grEccentricity 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];
grPlot(V,E); % the initial graph
title('\bfThe initial graph with weighed edges')
[Ec,Rad,Diam,Cv,Pv]=grEccentricity(E(:,1:2)); % the nonweighted task
fprintf('The nonweighted eccentricities of all vertexes:\n N ver Ecc\n')
fprintf('%4.0f %4.0f\n',[1:size(V,1);Ec])
fprintf('The radius of graph Rad=%d\n',Rad)
fprintf('The diameter of graph Diam=%d\n',Diam)
fprintf('The center vertexes is:')
fprintf(' %d',Cv)
fprintf('\nThe periphery vertexes is:')
fprintf(' %d',Pv)
fprintf('\n')
[Ec,Rad,Diam,Cv,Pv]=grEccentricity(E); % the weighted task
fprintf('The weighted eccentricities of all vertexes:\n N ver Ecc\n')
fprintf('%4.0f %4.0f\n',[1:size(V,1);Ec])
fprintf('The radius of graph Rad=%d\n',Rad)
fprintf('The diameter of graph Diam=%d\n',Diam)
fprintf('The center vertexes is:')
fprintf(' %d',Cv)
fprintf('\nThe periphery vertexes is:')
fprintf(' %d',Pv)
fprintf('\n')
case 11, % grIsEulerian test
disp('The grIsEulerian 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];
[eu,cEu]=grIsEulerian(E);
switch eu,
case 1,
st='';
E=[E(cEu,1:2), [1:size(E,1)]'];
case 0.5,
st='semi-';
E=[E(cEu,1:2), [1:size(E,1)]'];
otherwise,
st='not ';
E=[E(:,1:2), [1:size(E,1)]'];
end
grPlot(V,E,'g','','%d');
title(['\bf This graph is ' st 'Eulerian'])
V=[0 4;1 4;2 4;3 3.7;4 4;0 3;1 3.3;2 3.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;3 5;6 1;2 7;8 2;3 8;9 4;9 5;...
10 4;10 5;7 6;8 7;6 9;20 15;11 16;21 18;19 23;...
8 9;10 9;11 6;7 12;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;...
19 18;19 20;21 16;17 22;18 22;18 23;19 24;20 25;...
21 22;22 21;23 24;24 23;24 25];
[eu,cEu]=grIsEulerian(E);
switch eu,
case 1,
st='';
E=[E(cEu,1:2), [1:size(E,1)]'];
case 0.5,
st='semi-';
E=[E(cEu,1:2), [1:size(E,1)]'];
otherwise,
st='not ';
E=[E(:,1:2), [1:size(E,1)]'];
end
grPlot(V,[E,[1:size(E,1)]'],'g','');
title(['\bf This graph is ' st 'Eulerian'])
V=[0 4;1 4;2 4;3 3.7;4 4;0 3;1 3.3;2 3.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;3 5;6 1;2 7;8 2;3 8;9 4;9 5;...
10 4;10 5;7 6;8 7;6 9;20 15;11 16;21 18;19 23;...
8 9;10 9;11 6;7 12;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;...
19 18;19 20;21 16;17 22;18 22;18 23;19 24;20 25;...
21 22;22 21;23 24;24 25];
[eu,cEu]=grIsEulerian(E);
switch eu,
case 1,
st='';
E=[E(cEu,1:2), [1:size(E,1)]'];
case 0.5,
st='semi-';
E=[E(cEu,1:2), [1:size(E,1)]'];
otherwise,
st='not ';
E=[E(:,1:2), [1:size(E,1)]'];
end
grPlot(V,[E,[1:size(E,1)]'],'g','');
title(['\bf This graph is ' st 'Eulerian'])
case 12, % grIsomorph test
disp('The grIsomorph test')
V1=[0 0;1 0;2 0;0 1;1 1;2 1];
E1=[1 4;1 5;1 6;2 4;2 5;2 6;3 4;3 5;3 6];
V2=[cos([1:6]*pi/3);sin([1:6]*pi/3)]';
E2=[1 2;2 3;3 4;4 5;5 6;6 1;1 4;2 5;3 6];
grPlot(V1,E1,'g','%d','');
title('\bfThe graph 1')
grPlot(V2,E2,'g','%d','');
title('\bfThe graph 2')
[IsIsomorph,Permut]=grIsomorph(E1,E2);
if IsIsomorph,
disp('Their graphs are isomorphic:')
fprintf('Number of vertexes:\n V1 V2\n')
fprintf(' %3.0f %3.0f\n',[[1:max(E1(:))];Permut'])
else
disp('Their graphs are nonisomorphic')
end;
case 13, % grMaxComSu test
disp('The grMaxComSu test')
V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
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(:,1:2),E,'g','%d',''); % the initial graph
title('\bfThe initial graph')
grPlot(V,E,'g','%d',''); % the initial graph
title('\bfThe initial graph with weighed vertexes')
nMS=grMaxComSu(E); % the maximal complete sugraph
fprintf('Number of vertexes on the maximal complete sugraph = %d\n',...
length(nMS));
disp('In a maximal complete sugraph is the vertexes with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
nMS=grMaxComSu(E,V(:,3)); % the weightd maximal complete sugraph
fprintf(['Number of vertexes on the weighed maximal complete sugraph '...
'= %d\n'],length(nMS));
disp('In a weighed maximal complete sugraph is the vertexes with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
case 14, % grMaxFlows test
disp('The grMaxFlows 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 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
s=1; % the network source
t=11; % the network sink
fprintf('The source of the net s=%d\nThe sink of the net t=%d\n',s,t)
grPlot(V,E,'d','','%d'); % the initial digraph
title('\bfThe digraph of the net')
[v,mf]=grMaxFlows(E,s,t); % the maximal flow
disp('The solution of the maximal flows problem')
disp(' N arrow flow')
fprintf(' %2.0f %12.8f\n',[[1:length(v)];v'])
fprintf('The maximal flow =%12.8f\n',mf)
grPlot(V,[E(:,1:2),v],'d','','%6.4f'); % plot the digraph
title('\bfThe flows on the arrows')
case 15, % grMaxMatch test
disp('The grMaxMatch 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 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
grPlot(V,E,'g','','%d'); % the initial graph
title('\bfThe initial graph with weighed edges')
nMM=grMaxMatch(E(:,1:2)); % the maximal matching
fprintf('Number of edges on the maximal matching = %d\n',...
length(nMM));
disp('In a maximal matching is the edges with numbers:');
fprintf('%d ',nMM);
fprintf('\nThe total weight = %d\n',sum(E(nMM,3)));
grPlot(V,E(nMM,:),'g','','%d'); % the maximal matching
title('\bfThe maximal matching')
nMM=grMaxMatch(E); % the weighed maximal matching
fprintf('Number of edges on the weighed maximal matching = %d\n',...
length(nMM));
disp('In a weighed maximal matching is the edges with numbers:');
fprintf('%d ',nMM);
fprintf('\nThe total weight = %d\n',sum(E(nMM,3)));
grPlot(V,E(nMM,:),'g','','%d'); % the weighed maximal matching
title('\bfThe weighed maximal matching')
case 16, % grMaxStabSet test
disp('The grMaxStabSet test')
V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
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(:,1:2),E,'g','%d',''); % the initial graph
title('\bfThe initial graph')
nMS=grMaxStabSet(E); % the maximal stable set
fprintf('Number of vertexes on the maximal stable set = %d\n',...
length(nMS));
disp('In a maximal stable set is the vertexes with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
grPlot(V,E,'g','%d',''); % the initial graph
title('\bfThe initial graph with weighed vertexes')
nMS=grMaxStabSet(E,V(:,3)); % the weightd maximal stable set
fprintf(['Number of vertexes on the weighed maximal stable set '...
'= %d\n'],length(nMS));
disp('In a weighed maximal stable set is the vertexes with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
case 17, % grMinAbsEdgeSet test
disp('The grMinAbsEdgeSet 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 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 4;...
9 10 5;8 11 5;9 11 4;10 11 4]; % arrows and weights
grPlot(V,E,'g','','%d'); % the initial graph
title('\bfThe initial graph with weighed edges')
nMS=grMinAbsEdgeSet(E(:,1:2)); % the minimal absorbant set of edges
fprintf('Number of edges on the minimal absorbant set = %d\n',...
length(nMS));
disp('In a minimal absorbant set is the edges with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(E(nMS,3)));
grPlot(V,E(nMS,:),'g','','%d'); % the minimal absorbant set of edges
title('\bfThe minimal absorbant set of edges')
nMS=grMinAbsEdgeSet(E); % the minimal weighed absorbant set of edges
fprintf('Number of edges on the minimal weighed absorbant set = %d\n',...
length(nMS));
disp('In a minimal weighed absorbant set is the edges with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(E(nMS,3)));
grPlot(V,E(nMS,:),'g','','%d'); % the minimal weighed absorbant set of edges
title('\bfThe minimal weighed absorbant set of edges')
case 18, % grMinAbsVerSet test
disp('The grMinAbsVerSet test')
V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
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(:,1:2),E,'g','%d',''); % the initial graph
title('\bfThe initial graph')
grPlot(V,E,'g','%d',''); % the initial graph
title('\bfThe initial graph with weighed vertexes')
nMS=grMinAbsVerSet(E); % the minimal absorbant set of vertexes
fprintf('Number of vertexes on the minimal absorbant set = %d\n',...
length(nMS));
disp('In a minimal absorbant set is the vertexes with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
nMS=grMinAbsVerSet(E,V(:,3)); % the weightd minimal absorbant set of vertexes
fprintf(['Number of vertexes on the weighed minimal absorbant set '...
'= %d\n'],length(nMS));
disp('In a weighed minimal absorbant set is the vertexes with numbers:');
fprintf('%d ',nMS);
fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
case 19, % grMinCutSet test
disp('The grMinCutSet 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 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
s=1; % the network source
t=11; % the network sink
fprintf('The source of the net s=%d\nThe sink of the net t=%d\n',s,t)
grPlot(V,E,'d','','%d'); % the initial digraph
title('\bfThe digraph of the net')
[nMCS,mf]=grMinCutSet(E,s,t); % the minimal cut-set
fprintf('The first minimal cut-set include arrows:');
fprintf(' %d',nMCS);
fprintf(['\nThe maximal flow through '...
'each minimal cut-set = %12.6f\n'],mf)
grPlot(V,E(setdiff(1:size(E,1),nMCS),:),'d','','%d');
title('\bfThe digraph without first minimal cut-set')
case 20, % grMinEdgeCover test
disp('The grMinEdgeCover 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 and weights
E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;2 6 2;3 6 5;...
3 7 2;4 7 3;5 6 1;6 7 1;5 8 5;6 8 2;6 9 3;7 9 2;...
7 10 3;8 9 2;9 10 2;8 11 5;9 11 4;10 11 4]; % edges and weights
grPlot(V,E,'g',''); % the initial graph
title('\bfThe initial graph with weighed edges')
nMC=grMinEdgeCover(E(:,1:2)); % the minimal edge covering
fprintf('Number of edges on the minimal edge covering = %d\n',...
length(nMC));
disp('In a minimal edge cover is the edges with numbers:');
fprintf('%d ',nMC);
fprintf('\nThe total weight = %d\n',sum(E(nMC,3)));
grPlot(V,E(nMC,:),'g',''); % the minimal edge covering
title('\bfThe minimal edge covering')
nMC=grMinEdgeCover(E); % the weighed minimal edge covering
fprintf('Number of edges on the weighed minimal edge covering = %d\n',...
length(nMC));
disp('In a weighed minimal edge cover is the edges with numbers:');
fprintf('%d ',nMC);
fprintf('\nThe total weight = %d\n',sum(E(nMC,3)));
grPlot(V,E(nMC,:),'g',''); % the weighed minimal edge covering
title('\bfThe weighed minimal edge covering')
case 21, % grMinSpanTree test
disp('The grMinSpanTree 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 8;...
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];
grPlot(V,E); % the initial graph
title('\bfThe initial graph with weighed edges')
nMST=grMinSpanTree(E(:,1:2)); % the spanning tree
fprintf('Number of edges on the spanning tree = %d\n',length(nMST));
fprintf('The total weight = %d\n',sum(E(nMST,3)));
grPlot(V,E(nMST,:)); % the spanning tree
title('\bfThe spanning tree')
nMST=grMinSpanTree(E); % the minimal spanning tree
fprintf('Number of edges on the minimal spanning tree = %d\n',...
length(nMST));
fprintf('The total weight = %d\n',sum(E(nMST,3)));
grPlot(V,E(nMST,:)); % the minimal spanning tree
title('\bfThe minimal spanning tree')
case 22, % grMinVerCover test
disp('The grMinVerCover test')
V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
3 0 7;3 -1 1;4 0 5]; % vertexes coordinates and weights
E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;6 5;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 with weighed vertexes')
nMC=grMinVerCover(E); % the minimal vertex cover
fprintf('Number of vertexes on the minimal vertex cover = %d\n',...
length(nMC));
disp('In a minimal vertex cover is the vertexes with numbers:');
fprintf('%d ',nMC);
fprintf('\nThe total weight = %d\n',sum(V(nMC,3)));
grPlot(V(nMC,:)); % the solution of the MinVerCover problem
title('\bfThe minimal vertex cover')
nMC=grMinVerCover(E,V(:,3)); % the weightd minimal vertex cover
fprintf(['Number of vertexes on the weighed minimal vertex cover '...
'= %d\n'],length(nMC));
disp('In a weighed minimal vertex cover is the vertexes with numbers:');
fprintf('%d ',nMC);
fprintf('\nThe total weight = %d\n',sum(V(nMC,3)));
grPlot(V(nMC,:)); % the solution of the weighed MinVerCover problem
title('\bfThe weighed minimal vertex cover')
case 23, % grPERT test
disp('The grPERT test')
V=[1 1;0 0;1 0;1 -1;2 1;2 0;2 -1;3 1;...
4 0;3 -1;3 0]; % events coordinates
E=[2 1 5;2 3 5;2 4 5;1 3 2;3 4 2;1 5 3;...
1 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
5 8 5;6 8 2;6 11 3;7 11 2;7 10 3;8 11 2;...
11 10 2;8 9 5;11 9 4;10 9 4]; % works and their times
grPlot(V,E,'d','%d','%d');
title('\bfThe schema of project')
[CrP,Ts,Td]=grPERT(E);
grPlot([V Ts'],[CrP(1:end-1);CrP(2:end)]','d','%d','');
title('\bfThe critical path and start times for events')
grPlot([V Ts'],[E(:,1:2) Td],'d','%d','%d')
title('\bfThe start times for events and delay times for works')
case 24, % grPlot test
disp('The grPlot test')
V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
E=[1 2 5;1 1 2;1 1 5;2 2 3;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;2 6 2;3 6 5;3 7 2;...
4 7 3;5 6 1;6 7 1;5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
9 10 2;8 11 5;9 11 4;10 11 4;1 2 8;1 3 4;1 3 5;1 3 6]; % edges (arrows) and weights
grPlot(V(:,1:2),E,'d');
title('\bfThe digraph with weighed multiple arrows and loops')
grPlot(V,E(:,1:2),[],'%d','');
title('\bfThe graph with weighed vertexes without edges numeration')
grPlot(V(:,1:2));
title('\bfThe disconnected graph')
grPlot([],fullfact([5 5]),'d','','',0.8)
title('\bfThe directed clique\rm \itK\rm_5')
case 25, % grShortPath test
disp('The grShortPath 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 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
s=1; % the network source
t=11; % the network sink
fprintf('The source of the net s=%d\nThe sink of the net t=%d\n',s,t)
grPlot(V(:,1:2),E,'d','','%d');
title('\bfThe digraph with weighed edges')
[dSP,sp]=grShortPath(E,s,t);
disp('The shortest paths between all vertexes:');
fprintf(' %2.0f',1:size(dSP,2));
fprintf('\n');
for k1=1:size(dSP,1),
fprintf('%2.0f',k1)
fprintf('%6.2f',dSP(k1,:))
fprintf('\n')
end
grPlot(V(:,1:2),[sp(1:end-1);sp(2:end)]','d','%d','')
title(['\bfThe shortest path from vertex ' ...
num2str(s) ' to vertex ' num2str(t)])
case 26, % grShortVerPath test
disp('The grShortVerPath test')
V=[-8 0; -8 1; -7 0; -7 1; -6 0; -6 1; -6 2; -5 2; -4 1; -3 2;
-3 1; -2 0; -2 1; -1 2; 0 1; 0 2];
E=[1 3; 2 4; 3 5; 3 6; 4 6; 4 7; 5 9; 6 9; 7 8; 8 9; 8 10; 9 11;
11 12; 11 13; 10 14; 13 14; 13 15; 14 16];
V(:,3)=[5;9;1;2;2;4;9;9;1;4;6;5;7;7;3;5];
grPlot(V,E,'d','','',3);
title('\bfThe digraph with weighted vertices')
[dMWP,ssp]=grShortVerPath(E,V(:,3)); % solution
E1=repmat(dMWP(2:end-1),2,1);
E2=[dMWP(1); E1(:); dMWP(end)];
E3=reshape(E2,2,length(E2)/2)';
disp('The Minimal Vertexes Path:')
fprintf('%d ',dMWP)
fprintf('\nThe total weight = %d\n',ssp)
grPlot(V,E3,'d','','',3)
title('\bfThe Minimal Vertexes Weight Path')
case 27, % grTranClos test
disp('The grTranClos test')
V=[0 0;1 1;1.2 0.2;1 -1;2 1.2;2.2 0.2;2 -1.2;3 1;...
3.2 -0.2;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]; % arrows
grPlot(V,E,'d','%d','');
title('\bfThe initial digraph')
Ecl=grTranClos(E); % solution
grPlot(V,Ecl,'d','%d','');
title('\bfThe transitive closure for the digraph E')
case 28, % grTravSale test
disp('The grTravSale test')
C=[0 3 7 4 6 4;4 0 3 7 8 5;6 9 0 3 2 1;...
8 6 3 0 9 8;3 7 4 6 0 4;4 5 8 7 2 0];
disp('The distances between cities:')
fprintf(' %18.0f',1:size(C,2))
fprintf('\n')
for k1=1:size(C,1),
fprintf('%2.0f',k1)
fprintf('%20.12f',C(k1,:))
fprintf('\n')
end
[pTS,fmin]=grTravSale(C);
disp('The order of cities:')
fprintf('%d ',pTS)
fprintf('\nThe minimal way =%3.0f\n',fmin)
otherwise,
error('Select the test')
end