test_benchmark.m

都是测试程序

function out=test_benchmark

%
% David Gleich
% Copyright, Stanford University, 2007
%

% 
% 9 July 2007
% Initial version
%

%% History

%% 
%  2008-10-07, Version 2.1, Matlab 2007b, boost 1.33.0, 
%    g++-3.4 (lib), gcc-? (mex)
%         airfoil       west    cs-stan    minneso      tapir   
%  large   0.223 s    0.024 s    0.390 s    0.073 s    0.046 s  
%    med     NaN s    0.955 s      NaN s      NaN s    6.621 s  
%  small     NaN s    0.758 s      NaN s      NaN s      NaN s  

%% 
%  2008-10-07: Version 3.0, Matlab 2007b, boost 1.34.1, 
%    g++-4.0 (lib), gcc-? (mex)
%
%         airfoil       west    cs-stan    minneso      tapir   
%  large   0.183 s    0.017 s    0.222 s    0.048 s    0.037 s  
%    med     NaN s    0.593 s      NaN s      NaN s    3.901 s  
%  small     NaN s    0.543 s      NaN s      NaN s      NaN s  

%% 
%  2008-10-07: Version 4.0, Matlab 2007b, Boost 1.36.0,
%    g++-3.4 (lib) and gcc-4.1 (mex)
%
%         airfoil       west    cs-stan    minneso      tapir   
%  large   0.151 s    0.019 s    0.260 s    0.054 s    0.031 s  
%    med     NaN s    0.673 s      NaN s      NaN s    4.459 s  
%  small     NaN s    0.665 s      NaN s      NaN s      NaN s 

%% Benchmarks for MatlabBGL
% This function computes a series of benchmarks 

%% Create tests
% There are three types of tests, large scale, medium scale, and small
% scale.  
nrep = 10;
rand('state',0);

%% Setup results output
r.dt_large = 0;
r.dt_med = 0;
r.dt_small = 0;
testi = 1;

%% airfoil mesh
% Forming the sparse adjacency matrix and making it positive definite
af = load('airfoil');
n = max(max(af.i),max(af.j));
A = sparse(af.i,af.j,-1,n,n);
A = A + A';
d = abs(sum(A)) + 1;
A = A + diag(sparse(d));

r.name = 'airfoil'; fprintf('Graph: %s\n', r.name);
r.dt_large = bench_large(A,nrep);
r.dt_med = NaN;
r.dt_small = NaN;

results(testi) = r;
testi = testi+1;

%% west0479 matrix
load west0479;
A = west0479;

r.name = 'west'; fprintf('Graph: %s\n', r.name);
r.dt_large = bench_large(A,nrep);
r.dt_med = bench_medium(A,nrep);
r.dt_small = bench_small(A,nrep);

results(testi) = r;
testi = testi+1;

%% cs-stanford matrix
load('../graphs/cs-stanford');

r.name = 'cs-stan'; fprintf('Graph: %s\n', r.name);
r.dt_large = bench_large(A,nrep);
r.dt_med = NaN;
r.dt_small = NaN;

results(testi) = r;
testi = testi+1;

%% minnesota
load('../graphs/minnesota');

r.name = 'minneso'; fprintf('Graph: %s\n', r.name);
r.dt_large = bench_large(A,nrep);
r.dt_med = NaN;
r.dt_small = NaN;

results(testi) = r;
testi = testi+1;

%% tapir
load('../graphs/tapir');

r.name = 'tapir'; fprintf('Graph: %s\n', r.name);
r.dt_large = bench_large(A,nrep);
r.dt_med = bench_medium(A,nrep);
r.dt_small = NaN;

results(testi) = r;
testi = testi+1;

%% display results
fprintf('%5s ', ''); cellfun(@(s) fprintf(' %7s   ', s), {results.name}); fprintf('\n');
fprintf('%5s ','large'); fprintf('%7.3f s  ', [results.dt_large]); fprintf('\n');
fprintf('%5s ','med');   fprintf('%7.3f s  ', [results.dt_med]); fprintf('\n');
fprintf('%5s ','small');   fprintf('%7.3f s  ', [results.dt_small]); fprintf('\n');

if nargout > 1
    out = results;
end

end

    function dt=bench_large(A,nrep)
        As = spones(A);
        Asym = A+A';

        dt = 0;
        tic;
        for ri=1:nrep
            c=components(A);
        end
        op_dt = toc;
        dt = dt + op_dt;

        fprintf('  %30s: %7.3f s\n', 'components', op_dt);

        dt = 0;
        tic;
        for ri=1:nrep
            c=biconnected_components(Asym);
        end
        op_dt = toc;
        dt = dt + op_dt;

        fprintf('  %30s: %7.3f s\n', 'biconnect_components', op_dt);
        
        tic;
        for ri=1:nrep
            u = ceil(rand(1)*size(A,1)); v = ceil(rand(1)*size(A,1));
            f=max_flow(As,u,v);
        end
        op_dt = toc;
        dt = dt + op_dt;

        fprintf('  %30s: %7.3f s\n', 'max_flow', op_dt);
 
        tic;
        for ri=1:nrep
            u = ceil(rand(1)*size(A,1)); v = ceil(rand(1)*size(A,1));
            [i j v] = mst(Asym);
        end
        op_dt = toc;
        dt = dt + op_dt;

        fprintf('  %30s: %7.3f s\n', 'mst', op_dt);
    end

    function dt=bench_medium(A,nrep)
        dt = 0;
        tic;
        for ri=1:nrep
            bc=betweenness_centrality(spones(A));
        end
        op_dt = toc;
        dt = dt + op_dt;

        fprintf('  %30s: %7.3f s\n', 'betweenness_centrality', op_dt);
    end

    function dt=bench_small(A,nrep)
        dt = 0;
        tic;
        for ri=1:nrep
            bc=all_shortest_paths(spones(A));
        end
        op_dt = toc;
        dt = dt + op_dt;

        fprintf('  %30s: %7.3f s\n', 'all_shortest_paths', op_dt);
    end