function d = matbfs(A,i)
% MATBFS Breadth-first search using matrix-vector products
% 
% d = matbfs(A,i) returns the breadth-first search distance from a 
% vertex i to all reachable vertices in the graph.  Right now, this 
% function only works for undirected graphs
%
% Example:
%   % requires MatlabBGL
%   

% David F. Gleich
% Purdue University Networks & Matrix Computations sample code
% 2011-09-08

n = size(A,1);

if size(A,1) ~= size(A,2), error('matbfs:argumentError',...
	'the input is not a square matrix'); end
if i<1 || i>n, error('matbfs:argumentError',...
	'the starting vertex %i is not in [1,%i]',i, n); end

d = Inf*ones(n,1); % all distances are infinite initially
x = zeros(n,1);
x(i) = 1; 
d(i) = 0;
y = zeros(n,1);

for step=1:n
    y = A*x;
	newverts = y & ~x;
	d(newverts) = step;
	if ~any(newverts), break; end % we are done with no new vertices
	x = x|y;
end
