stanford研究组开发的图论工具箱matlab_bgl

stanford的研究组开发了一个很不错的图论工具箱，matlab_bgl，使用了Boost图论库，稳定快速，是个比较实用的工具（最新的程序库运行在matlab7.0以上），可以结合这个程序包学习一下图论的一些算法。 http://www.stanford.edu/~dgleich/programs/matlab_bgl/

function [DP] = all_shortest_paths（Avarargin）
% 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（ij） indicates the shortest path distance between vertex i and
% vertex j.  
% 
% ... = all_shortest_paths（Auoptions） 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}]
%   options.edge_weight: a double array over the edges with an edge
%       weight for each node see EDGE_INDEX and EXAMPLES/REWEIGHTED_GRAPHS
%       for information on how to use this option correctly
%       [{‘matrix‘} | length（nnz（A）） double vector]
%
% 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（Astruct（‘algname‘‘johnson‘））
%
% See also JOHNSON_ALL_SP FLOYD_WARSHALL_ALL_SP.

%
% David Gleich
% 19 April 2006
%
% 2006-05-31
% Added full2sparse check
%
% 1 March 2007
% Added option for predecessor matrix from floyd_warshall
%
% 20 April 2007
% Added edge weight option
%
% 8 July 2007
% Fixed typos in strings and documentation
% Removed fixes for the Johnson algorithm
%
% 12 July 2007
% Fixed edge_weight documentation.
%
% 21 July 2007
% Fixed divide by 0 error 
%

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

options = struct（‘algname‘ ‘auto‘ ‘inf‘ Inf ‘edge_weight‘ ‘matrix‘）;
if （~isempty（varargin））
    options = merge_structs（varargin{1} options）;
end

% edge_weights is an indicator that is 1 if we are using edge_weights
% passed on the command line or 0 if we are using the matrix.
%edge_weights = 0;
edge_weight_opt = ‘matrix‘;

if strcmp（options.edge_weight ‘matrix‘）
    % do nothing if we are using the matrix weights
else
    edge_weight_opt = options.edge_weight;
end

if （check）
    % check the values of the matrix
    check_matlab_bgl（Astruct（‘values‘1））;
    
    % set the algname
    if （strcmpi（options.algname ‘auto‘））
        nz = nnz（A）;
        if （nz/（numel（A）+1） > .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

if nargout > 1
    [DP] = matlab_bgl_all_sp_mex（Alower（options.algname）options.infedge_weight_opt）;
    P = P‘;
else
    D = matlab_bgl_all_sp_mex（Alower（options.algname）options.infedge_weight_o

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        245  2007-07-22 08:47  matlab_bgl\@inplace\assign.m

     文件        195  2007-07-22 08:47  matlab_bgl\@inplace\display.m

     文件        319  2007-07-22 08:47  matlab_bgl\@inplace\double.m

     文件        239  2007-07-22 08:47  matlab_bgl\@inplace\end.m

     文件        766  2007-07-22 08:47  matlab_bgl\@inplace\inplace.m

     文件        228  2007-07-22 08:47  matlab_bgl\@inplace\size.m

     文件        269  2007-07-22 08:47  matlab_bgl\@inplace\subsasgn.m

     文件        687  2007-07-22 08:47  matlab_bgl\@inplace\subsref.m

     文件        276  2007-07-22 08:47  matlab_bgl\@ipdouble\ipdouble.m

     文件        269  2007-07-22 08:47  matlab_bgl\@ipint32\ipint32.m

     文件       3036  2007-07-22 09:14  matlab_bgl\all_shortest_paths.m

     文件       3539  2007-07-22 08:47  matlab_bgl\astar_search.m

     文件       1472  2007-07-22 08:47  matlab_bgl\bellman_ford_sp.m

     文件       3447  2008-10-29 23:34  matlab_bgl\betweenness_centrality.m

     文件       1672  2007-07-22 08:47  matlab_bgl\bfs.m

     文件       2114  2007-07-22 08:47  matlab_bgl\biconnected_components.m

     文件       2440  2007-07-22 08:47  matlab_bgl\breadth_first_search.m

     文件       3623  2007-07-22 08:47  matlab_bgl\clustering_coefficients.m

     文件       3002  2007-07-22 08:47  matlab_bgl\combine_visitors.m

     文件       1398  2007-07-22 08:47  matlab_bgl\components.m

     文件       3764  2007-07-22 08:47  matlab_bgl\Contents.m

     文件       3046  2007-07-22 09:18  matlab_bgl\core_numbers.m

     文件       1509  2007-07-22 08:47  matlab_bgl\custom\dijkstra_all_sp.m

     文件       1000  2007-07-22 08:47  matlab_bgl\cycle_graph.m

     文件       1089  2007-07-22 08:47  matlab_bgl\dag_sp.m

     文件       2794  2007-07-22 08:47  matlab_bgl\depth_first_search.m

     文件       2206  2007-07-22 08:47  matlab_bgl\dfs.m

     文件       1467  2007-07-22 08:47  matlab_bgl\dijkstra_sp.m

     文件       2387  2007-07-22 08:47  matlab_bgl\doc\changed.txt

     文件       3892  2007-07-22 08:47  matlab_bgl\doc\html\changes.html

............此处省略368个文件信息