function connected = graph_adj_is_nodewise_connected_breadth ( A )

%*****************************************************************************80
%
%% graph_adj_is_nodewise_connected_breadth() determines if a graph is nodewise connected.
%
%  Discussion:
%
%    A graph is (nodewise) connected if, from every node, there is a path
%    to any other node.
%
%    This function performs a breadth-first search of the graph.  
%    The nodes of the graph are to be collected into levels.
%    Let node 1 be level 1.
%    Level 2 is the immediate neigbors of level 1 not in any previous level.
%    Level k+1 is the immediate neighbors of level k not in any previous level.
%    If a given level produces no nodes, we stop.
%    If, after stopping, we have encountered all nodes, the graph is connected.
%
%  Licensing:
%
%    This code is distributed under the MIT license. 
%
%  Modified:
%
%    30 August 2022
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer A(n,n), the adjacency matrix for the graph.
%
%  Output:
%
%    logical connected: is true if the graph is connected.
%
  value = matrix_is_adjacency ( A );
  if ( ~ value )
    fprintf ( 1, '\n' );
    fprintf ( 1, 'graph_adj_is_nodewise_connected_breadth(): Fatal error!\n' );
    fprintf ( 1, '  The input is not a legal adjacency matrix.\n' );  
    error ( 'graph_adj_is_nodewise_connected_breadth(): Fatal error!\n' );
  end

  n = size ( A, 1 );
%
%  FOUND(I) is 1 if node I has been reached.
%  LIST(I) contains a list of the nodes as they are reached.
%
  list = zeros(1:n);
  found = zeros(1:n);
%
%  Start at node 1.
%
  found(1) = true;
  list(1) = 1;
  ilo = 1;
  ihi = 1;
%
%  From the batch of nodes found last time, LIST(ILO:IHI),
%  look for unfound neighbors, and store their indices in LIST(JLO:JHI).
%
  while ( true )

    jlo = ihi + 1;
    jhi = ihi;
%
%  Consider all nodes found on previous pass.
%
    for ii = ilo : ihi

      i = list(ii);
%
%  For each new node I, consider its J-th neighbor.
%
      for j = 1 : n

        if ( A(i,j) )

          if ( ~ found(j) )
            jhi = jhi + 1;
            list(jhi) = j;
            found(j) = true;
          end

        end

      end

    end
%
%  If no neighbors were found on this pass, our search is complete.
%  The graph is connected if we encountered every node.
%
    if ( jhi < jlo )
      connected = ( ihi == n );
      break
    end
%
%  If neighbors were found, repeat the loop.
%
    ilo = jlo;
    ihi = jhi;

  end

  return
end
