//

 //=======================================================================

 // Copyright 1997-2001 University of Notre Dame.

 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

 //

 // Distributed under the Boost Software License, Version 1.0. (See

 // accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 //=======================================================================

 //

 #ifndef BOOST_INCREMENTAL_COMPONENTS_HPP

 #define BOOST_INCREMENTAL_COMPONENTS_HPP

 #include <boost/detail/iterator.hpp>

 #include <boost/graph/detail/incremental_components.hpp>

 namespace boost {

   // A connected component algorithm for the case when dynamically

   // adding (but not removing) edges is common.  The

   // incremental_components() function is a preparing operation. Call

   // same_component to check whether two vertices are in the same

   // component, or use disjoint_set::find_set to determine the

   // representative for a vertex.

   // This version of connected components does not require a full

   // Graph. Instead, it just needs an edge list, where the vertices of

   // each edge need to be of integer type. The edges are assumed to

   // be undirected. The other difference is that the result is stored in

   // a container, instead of just a decorator.  The container should be

   // empty before the algorithm is called. It will grow during the

   // course of the algorithm. The container must be a model of

   // BackInsertionSequence and RandomAccessContainer

   // (std::vector is a good choice). After running the algorithm the

   // index container will map each vertex to the representative

   // vertex of the component to which it belongs.

   //

   // Adapted from an implementation by Alex Stepanov. The disjoint

   // sets data structure is from Tarjan's "Data Structures and Network

   // Algorithms", and the application to connected components is

   // similar to the algorithm described in Ch. 22 of "Intro to

   // Algorithms" by Cormen, et. all.

   //  

   // RankContainer is a random accessable container (operator[] is

   // defined) with a value type that can represent an integer part of

   // a binary log of the value type of the corresponding

   // ParentContainer (char is always enough) its size_type is no less

   // than the size_type of the corresponding ParentContainer

   // An implementation of disjoint sets can be found in

   // boost/pending/disjoint_sets.hpp

   template <class EdgeListGraph, class DisjointSets>

   void incremental_components(EdgeListGraph& g, DisjointSets& ds)

   {

     typename graph_traits<EdgeListGraph>::edge_iterator e, end;

     for (tie(e,end) = edges(g); e != end; ++e)

       ds.union_set(source(*e,g),target(*e,g));

   }

   template <class ParentIterator>

   void compress_components(ParentIterator first, ParentIterator last)

   {

     for (ParentIterator current = first; current != last; ++current) 

       detail::find_representative_with_full_compression(first, current-first);

   }

   template <class ParentIterator>

   typename boost::detail::iterator_traits<ParentIterator>::difference_type

   component_count(ParentIterator first, ParentIterator last)

   {

     std::ptrdiff_t count = 0;

     for (ParentIterator current = first; current != last; ++current) 

       if (*current == current - first) ++count; 

     return count;

   }

   // This algorithm can be applied to the result container of the

   // connected_components algorithm to normalize

   // the components.

   template <class ParentIterator>

   void normalize_components(ParentIterator first, ParentIterator last)

   {

     for (ParentIterator current = first; current != last; ++current) 

       detail::normalize_node(first, current - first);

   }

   template <class VertexListGraph, class DisjointSets> 

   void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)

   {

     typename graph_traits<VertexListGraph>

       ::vertex_iterator v, vend;

     for (tie(v, vend) = vertices(G); v != vend; ++v)

       ds.make_set(*v);

   }

   template <class Vertex, class DisjointSet>

   inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)

   {

     return ds.find_set(u) == ds.find_set(v);

   }

   // considering changing the so that it initializes with a pair of

   // vertex iterators and a parent PA.

   template <class IndexT>

   class component_index

   {

   public://protected: (avoid friends for now)

     typedef std::vector<IndexT> MyIndexContainer;

     MyIndexContainer header;

     MyIndexContainer index;

     typedef typename MyIndexContainer::size_type SizeT;

     typedef typename MyIndexContainer::const_iterator IndexIter;

   public:

     typedef detail::component_iterator<IndexIter, IndexT, SizeT> 

       component_iterator;

     class component {

       friend class component_index;

     protected:

       IndexT number;

       const component_index<IndexT>* comp_ind_ptr;

       component(IndexT i, const component_index<IndexT>* p) 

         : number(i), comp_ind_ptr(p) {}

     public:

       typedef component_iterator iterator;

       typedef component_iterator const_iterator;

       typedef IndexT value_type;

       iterator begin() const {

         return iterator( comp_ind_ptr->index.begin(),

                          (comp_ind_ptr->header)[number] );

       }

       iterator end() const {

         return iterator( comp_ind_ptr->index.begin(), 

                          comp_ind_ptr->index.size() );

       }

     };

     typedef SizeT size_type;

     typedef component value_type;

 #if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)

     template <class Iterator>

     component_index(Iterator first, Iterator last) 

     : index(std::distance(first, last))

     { 

       std::copy(first, last, index.begin());

       detail::construct_component_index(index, header);

     }

 #else

     template <class Iterator>

     component_index(Iterator first, Iterator last) 

       : index(first, last)

     { 

       detail::construct_component_index(index, header);

     }

 #endif

     component operator[](IndexT i) const {

       return component(i, this);

     }

     SizeT size() const {

       return header.size();

     }

   };

 } // namespace boost

 #endif // BOOST_INCREMENTAL_COMPONENTS_HPP