all_shortest_paths.m

The MatlabBGL library fills a hole in Matlab s suite of algorithms. Namely, it provides a rich set o

function D = all_shortest_paths(A,varargin)
% all_shortest_paths Compute the weighted all pairs shortest path problem.
%
% D = all_shortest_paths(A) returns the distance matrix D for all vertices
% where D(i,j) indicates the shortest path distance between vertex i and
% vertex j.  
% 
% ... = all_shortest_paths(A,u,options) sets optional parameters (see 
% set_matlab_bgl_options) for the standard options.
%   options.algname:: the algorithm to use 
%       [{'auto'} | 'johnson' | 'floyd_warshall']
%   options.inf: the value to use for unreachable vertices 
%       [double > 0 | {Inf}]
%
% Note: 'auto' cannot be used with 'nocheck' = 1.  The 'auto' algorithms
% checks the number of edges in A and if the graph is more than 10% dense,
% it uses the Floyd-Warshall algorithm instead of Johnson's algorithm.
%
% Example:
%    load graphs/clr-26-1.mat
%    all_shortest_paths(A)
%    all_shortest_paths(A,struct('algname','johnson'))
%
% See also JOHNSON_ALL_SP, FLOYD_WARSHALL_ALL_SP.

%
% David Gleich
% 19 April 2006
%
% 2006-05-31: Added full2sparse check
%

[trans check full2sparse] = get_matlab_bgl_options(varargin{:});
if (full2sparse && ~issparse(A)) 
    A = sparse(A); 
end

options = struct('algname', 'auto', 'inf', Inf);
if (length(varargin) > 0)
    options = merge_structs(varargin{1}, options);
end;

if (check)
    % check the values of the matrix
    check_matlab_bgl(A,struct('values',1));
    
    % set the algname
    if (strcmpi(options.algname, 'auto'))
        nz = nnz(A);
        if (nz/numel(A) > .1)
            options.algname = 'floyd_warshall';
        else
            options.algname = 'johnson';
        end;
    end;
else
    if (strcmpi(options.algname, 'auto'))
        error('all_shortest_paths:invalidParameter', ...
            'algname auto is not compatible with no check');       
    end;
end;

if (trans)
    A = A';
end;

D = matlab_bgl_all_sp_mex(A,lower(options.algname),options.inf);

% Fix for the Johnson algorithm
if (strcmpi(options.algname,'johnson'))
    if (max(max(D)) > realmax - eps(realmax))
        D(D==realmax) = Inf;
        warning(['Due to an error in the johnson_all_pairs_shortest_paths\n' ...
            'function in Boost, we need to round the output back to Infinity\n' ...
            'this may cause problems with the output or change in future versions\n' ...
            'of MatlabBGL.  DO NOT DEPEND ON THIS BEHAVIOR%s\n'],'');
    end;
end;
D = D';