/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ident "$Project: polymake $$Id: connected.tcc 7315 2006-04-02 21:37:53Z gawrilow $"

#include <connected.h>
#include <list>

namespace polymake {
namespace graph {

   template <typename Graph>
   bool is_connected(const Graph& G)
   {
      const int nodes=G.nodes();
      int unvisited=nodes;
      Bitset visited(nodes);
      std::list<int> node_queue;

      node_queue.push_back(0);
      visited+=0; --unvisited;
    
      while (!node_queue.empty()) {
	 const int n=node_queue.front();      // remove first node from the queue and check it's neighbours.
	 node_queue.pop_front();
	 for (typename Entire<typename Graph::out_edge_list>::const_iterator e=entire(G.out_edges(n)); !e.at_end(); ++e) {
	    const int nn=e.to_node();
	    if (!visited.contains(nn)) {                // nn not been visited yet -> add nn to the queue.
	       visited+=nn;
	       if (--unvisited <= 0) return true;
	       node_queue.push_back(nn);
	    }
	 }
      }

      return unvisited==0;	// extra test due to possible exotic cases G.nodes()<=1
   }

   template <typename Graph>
   ConnectedComponents_iterator<Graph>::ConnectedComponents_iterator(const Graph& graph_arg)
      : graph(&graph_arg), not_visited(sequence(0,graph->nodes()))
   {
      get_next();
   }

   template <typename Graph>
   void ConnectedComponents_iterator<Graph>::rewind()
   {
      not_visited=sequence(0,graph->nodes());
      component.clear();
      get_next();
   }

   template <typename Graph>
   void ConnectedComponents_iterator<Graph>::get_next()
   {
      if (!not_visited.empty()) {
	 std::list<int> node_queue;
	 int n=not_visited.front();
	 node_queue.push_back(n);
	 component += n;
	 not_visited -= n;

	 while (!node_queue.empty()) {
	    n=node_queue.front();
	    node_queue.pop_front();

	    for (typename Entire<typename Graph::out_edge_list>::const_iterator e=entire(graph->out_edges(n));
		 !e.at_end(); ++e) {
	       const int nn=e.to_node();

	       if (not_visited.contains(nn)) {
		  not_visited -= nn;
		  component += nn;
		  node_queue.push_back(nn);
	       }
	    }
	 }
      }
   }
  
} }

// Local Variables:
// mode:C++
// c-basic-offset:3
// End: