/* Copyright (c) 1997-2004
   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.
*/

#ifndef _POLYMAKE_GRAPH_CONNECTED_H
#define _POLYMAKE_GRAPH_CONNECTED_H "$Project: polymake $$Id: connected.h 7315 2006-04-02 21:37:53Z gawrilow $"

#include <Set.h>
#include <Bitset.h>

namespace polymake { namespace graph {

   /// Determine whether an undirected graph is connected.
   template <typename Graph>
   bool is_connected(const Graph& G);

   template <typename Graph>
   class ConnectedComponents_iterator {
   protected:
      const Graph *graph;
      Set<int> component;
      Bitset not_visited;

      void get_next();
   public:
      typedef std::forward_iterator_tag iterator_category;
      typedef Set<int> value_type;
      typedef const value_type& reference;
      typedef const value_type* pointer;
      typedef ptrdiff_t difference_type;

      typedef ConnectedComponents_iterator iterator;
      typedef iterator const_iterator;

      ConnectedComponents_iterator() : graph(0) { }

      ConnectedComponents_iterator(const Graph& graph_arg);

      reference operator* () const { return component; }
      pointer operator-> () const { return &component; }

      iterator& operator++ ()
      {
	 component.clear();
	 get_next();
	 return *this;
      }
      const iterator operator++ (int) { iterator copy(*this);  operator++();  return copy; }

      bool operator== (const iterator& it) const { return component==it.component; }
      bool operator!= (const iterator& it) const { return !operator==(it); }

      bool at_end() const { return component.empty(); }

      void rewind();
   };

   template <typename GraphRef>
   class ConnectedComponents {
   protected:
      pm::alias<GraphRef> graph;
   public:
      typedef typename pm::alias<GraphRef>::arg_type arg_type;
      typedef typename pm::deref<GraphRef>::type Graph;

      ConnectedComponents(arg_type graph_arg) : graph(graph_arg) { }

      typedef ConnectedComponents_iterator<Graph> iterator;
      typedef iterator const_iterator;
      typedef typename iterator::value_type value_type;
      typedef const value_type reference;
      typedef reference const_reference;

      iterator begin() const { return iterator(graph); }
      iterator end() const { return iterator(); }
      reference front() const { return *begin(); }

      int size() const { return pm::count_it(begin()); }
      bool empty() const { return static_cast<const Graph&>(graph).nodes()==0; }
   };

   /// Compute the connected components
   template <typename Graph> inline
   ConnectedComponents<const Graph&> connected_components(const Graph& G) { return G; }
} }

namespace pm {
   template <typename Graph>
   struct check_iterator_feature< polymake::graph::ConnectedComponents_iterator<Graph>, end_sensitive > : True { };

   template <typename Graph>
   struct check_iterator_feature< polymake::graph::ConnectedComponents_iterator<Graph>, rewindable > : True { };

   template <typename GraphRef>
   struct spec_object_traits< polymake::graph::ConnectedComponents<GraphRef> >
      : spec_object_traits<is_container> { };
}

#include <connected.tcc>

#endif // _POLYMAKE_GRAPH_CONNECTED_H

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