grtheorytest.m

可求最短路径和最小边覆盖颠覆盖和旅行商问题的图论程序

% Test program for GrTheory functions
% Author: Sergiy Iglin
% e-mail: [e-mail]
% 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:\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)]'];