← Back to branch summary

~dgleich/matlab-bgl/master

« back to all changes in this revision

Viewing changes to all_shortest_paths.m

  • Committer: David Gleich
  • Date: 2008-09-29 22:06:39 UTC
  • mfrom: (1.1.19 work)
  • Revision ID: dgleich@stanford.edu-20080929220639-4ic8mxd20lu81dla
Incorporated misc. fixes and graph layout algorithms.

Show diffs side-by-side

added added

removed removed

Lines of Context:
all_shortest_paths.m
34
34
%
35
35
% See also JOHNSON_ALL_SP, FLOYD_WARSHALL_ALL_SP.
36
36
 
37
 
%
38
37
% David Gleich
39
 
% 19 April 2006
40
 
%
41
 
% 2006-05-31
42
 
% Added full2sparse check
43
 
%
44
 
% 1 March 2007
45
 
% Added option for predecessor matrix from floyd_warshall
46
 
%
47
 
% 20 April 2007
48
 
% Added edge weight option
49
 
%
50
 
% 8 July 2007
51
 
% Fixed typos in strings and documentation
52
 
% Removed fixes for the Johnson algorithm
53
 
%
54
 
% 12 July 2007
55
 
% Fixed edge_weight documentation.
56
 
%
57
 
% 21 July 2007
58
 
% Fixed divide by 0 error in check for algorithm type
59
 
%
60
 
% 2008-04-02: Added documenation for predecessor matrix
61
 
%
 
38
% Copyright, Stanford University, 2006-2008
 
39
 
 
40
%% History
 
41
%  2006-04-19: Initial version
 
42
%  2006-05-31: Added full2sparse check
 
43
%  2007-03-01: Added option for predecessor matrix from floyd_warshall
 
44
%  2007-04-20: Added edge weight option
 
45
%  2007-07-08: Fixed typos in strings and documentation
 
46
%    Removed fixes for the Johnson algorithm
 
47
%  2007-07-12: Fixed edge_weight documentation.
 
48
%  2007-07-21: Fixed divide by 0 error in check for algorithm type
 
49
%  2008-04-02: Added documenation for predecessor matrix
 
50
%%
62
51
 
63
52
[trans check full2sparse] = get_matlab_bgl_options(varargin{:});
64
 
if (full2sparse && ~issparse(A)) 
65
 
    A = sparse(A); 
66
 
end
 
53
if full2sparse && ~issparse(A), A = sparse(A); end
67
54
 
68
55
options = struct('algname', 'auto', 'inf', Inf, 'edge_weight', 'matrix');
69
 
if (~isempty(varargin))
70
 
    options = merge_structs(varargin{1}, options);
71
 
end
 
56
if ~isempty(varargin), options = merge_structs(varargin{1}, options); end
72
57
 
73
58
% edge_weights is an indicator that is 1 if we are using edge_weights
74
59
% passed on the command line or 0 if we are using the matrix.
81
66
    edge_weight_opt = options.edge_weight;
82
67
end
83
68
 
84
 
if (check)
 
69
if check
85
70
    % check the values of the matrix
86
71
    check_matlab_bgl(A,struct('values',1));
87
72
    
88
73
    % set the algname
89
 
    if (strcmpi(options.algname, 'auto'))
 
74
    if strcmpi(options.algname, 'auto')
90
75
        nz = nnz(A);
91
76
        if (nz/(numel(A)+1) > .1)
92
77
            options.algname = 'floyd_warshall';
95
80
        end
96
81
    end
97
82
else
98
 
    if (strcmpi(options.algname, 'auto'))
 
83
    if strcmpi(options.algname, 'auto')
99
84
        error('all_shortest_paths:invalidParameter', ...
100
85
            'algname auto is not compatible with no check');       
101
86
    end
102
87
end
103
88
 
104
 
if (trans)
105
 
    A = A';
106
 
end
 
89
if trans, A = A'; end
107
90
 
108
91
if nargout > 1
109
92
    [D,P] = matlab_bgl_all_sp_mex(A,lower(options.algname),options.inf,edge_weight_opt);
112
95
    D = matlab_bgl_all_sp_mex(A,lower(options.algname),options.inf,edge_weight_opt);
113
96
end
114
97
 
115
 
if trans
116
 
    D = D';
117
 
end
 
98
if trans, D = D'; end
118
99