function [d, pred, target] = bfs(adj_mat, s, directed, P)
% BFS Perform a breadth-first search of the graph.
%
% [D, PRED] = BFS(ADJ_MAT, S, DIRECTED) does a bfs starting from s.
% D(i) is the distance of node i from s.
% PRED(i) is the parent of i in the bfs tree rooted at start, or -1 if undefined.
% See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p470.
%
% [D, PRED, TARGET] = BFS(ADJ_MAT, S, DIRECTED, P) does a bfs from S until a node (TARGET) satisfying P is
% found; if none is found, TARGET = -1.

n = length(adj_mat);

if ~exist('P')
  P = zeros(1, n); % force exploration of whole graph
end

global white gray black
white = 0; gray = 1; black = 2;

color = zeros(1,n);
d = inf*ones(1,n);
pred = zeros(1,n);

color(s) = gray;
d(s) = 0;
pred(s) = -1;
Q = s;
target = -1;

while ~isempty(Q)
  u = Q(1);
  if P(u)
    target = u;
    return;
  end
  if directed
    ns = children(adj_mat, u);
  else
    ns = neighbors(adj_mat, u);
  end
  ns = ns(:)';
  for v=ns
    if color(v)==white
      color(v) = gray;
      d(v) = d(u) + 1;
      pred(v) = u;
      Q = [Q v];
    end
  end
  Q = Q(2:end);
  color(u) = black;
end
