function value = graph_connected ( adj )
%
%% GRAPH_CONNECTED is true if the graph G is connected.
%
%  ADJ(N,N) is the adjacency matrix for the graph G.
%
%  VALUE is output by the function:
%  TRUE (1), the graph is connected.
%  FALSE (0), the graph is not connected.
%

%
%  How many nodes are there?
%
  [ n, n ] = size ( adj );
%
%  REACH(I) will be TRUE if we can reach node I from node 1.
%
  reach = zeros(1,n);
  reach(1) = true;
%
%  NEW holds the nodes we have just reached on this step.
%
  new = [1];
%
%  REACHED counts how many nodes we have reached.
%
  reached = 1;
%
%  As long as NEW isn't empty, we reached some new nodes.
%  Use them as stepping stones, and try to reach more nodes.
%
  while ( 0 < length ( new ) )

    old = new;
    new = [];
%
%  For each node J that we found on the previous step...
%
    for k = 1 : length ( old )
      j = old(k);
%
%  ...look for adjacent neighbors I...
%
      for i = 1 : n

        if ( adj(i,j) == 1 )
%
%  ...and if node I hasn't been reached yet:
%  mark that is has been reached,
%  add it to list,
%  and increase the count of nodes we have reached.
%
          if ( ~ reach(i) )
            reach(i) = true;
            new = [ new, i ];
            reached = reached + 1;
          end

        end
      end

    end

  end
%
%  When we get here, we have reached all the nodes we can from node 1.
%
  value = ( reached == n );

  return
end
