breadth_first_search.m

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

function breadth_first_search(A,u,bfs_visitor,varargin)
% BREADTH_FIRST_SEARCH Fully wrap the Boost breadth_first_search call
% including the bfs_visitor.
%
% breadth_first_search(A,u,vis) performs a breadth first traversal 
% of A starting from vertex u.  For each event defined by the bfs_visitor 
% structure below, the visitor is called with the either the name of the 
% vertex (u), or the edge index and it's source and target (ei,u,v).  
%
% See http://www.boost.org/libs/graph/doc/BFSVisitor.html for a description
% of the events.
% 
% bfs_visitor is a struct with the following optional fields
%    vis.initialize_vertex(u)
%    vis.discover_vertex(u)
%    vis.examine_vertex(u)
%    vis.examine_edge(ei,u,v)
%    vis.tree_edge(ei,u,v)
%    vis.non_tree_edge(ei,u,v)
%    vis.gray_target(ei,u,v)
%    vis.black_target(ei,u,v)
%    vis.finish_vertex(u)
% Each bfs_visitor parameter should be a function pointer, which returns 0
% if the bfs should stop.  (If the function does not return anything, the
% bfs continues.)
%
% This method works on directed graphs.
% The runtime is O(V+E), excluding the complexity of the visitor
% operations.
%
% Realistically, this function must be used with the
% pass-by-reference/in-place modification library.  
%
% ... = breadth_first_search(A,u,vis,options) sets optional parameters (see 
% set_matlab_bgl_options) for the standard options.
%   There are no additional options for this function.
%
% Note: this function does not depend upon the non-zero values of A, but
% only uses the non-zero structure of A.
%
% Example:
%   This example finds the distance to a single point and stops the search.
%   function dist_uv(A,u,v,options)
%     vstar = v;
%     dmap = ipdouble(zeros(size(A,1),1));
%     function stop=on_tree_edge(ei,u,v)
%       dmap[v] = dmap[u]+1;
%       return (v ~= vstar);
%     end;
%     breadth_first_search(A,u,struct('tree_edge',@on_tree_edge),options);
%   end;
%
% See also BFS

%
% David Gleich
% 16 May 2006
%
% 2006-05-31: Added full2sparse check 
%

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

if (check)
    % no additional input checks
    check_matlab_bgl(A,struct());
end;

if (trans)
    A = A';
end;

%bfs_visitor = merge_structs(bfs_visitor, empty_bfs_visitor);

% The 101 is the flag for calling BFS, not DFS
bfs_dfs_vis_mex(A,u,bfs_visitor,101);