text: //
  //=======================================================================
  // Copyright 1997-2001 University of Notre Dame.
  // Copyright 2009 Trustees of Indiana University.
  // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
  //
  // 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>
  #include <boost/iterator/counting_iterator.hpp>
  #include <boost/make_shared.hpp>
  #include <boost/pending/disjoint_sets.hpp>
  #include <iterator>
  
  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.
    //  
  
    // 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 (boost::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 (boost::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);
    }
  
    // Class that builds a quick-access indexed linked list that allows
    // for fast iterating through a parent component's children.
    template <typename IndexType>
    class component_index {
  
    private:
      typedef std::vector<IndexType> IndexContainer;
  
    public:
      typedef counting_iterator<IndexType> iterator;
      typedef iterator const_iterator;
      typedef IndexType value_type;
      typedef IndexType size_type;
  
      typedef detail::component_index_iterator<typename IndexContainer::iterator>
        component_iterator;
  
    public:
      template <typename ParentIterator,
                typename ElementIndexMap>
      component_index(ParentIterator parent_start,
                      ParentIterator parent_end,
                      const ElementIndexMap& index_map) :
        m_num_elements(std::distance(parent_start, parent_end)),
        m_components(make_shared<IndexContainer>()),
        m_index_list(make_shared<IndexContainer>(m_num_elements)) {
  
        build_index_lists(parent_start, index_map);
        
      } // component_index
  
      template <typename ParentIterator>
      component_index(ParentIterator parent_start,
                      ParentIterator parent_end) :
        m_num_elements(std::distance(parent_start, parent_end)),
        m_components(make_shared<IndexContainer>()),
        m_index_list(make_shared<IndexContainer>(m_num_elements)) {
  
        build_index_lists(parent_start, boost::identity_property_map());
  
      } // component_index
  
      // Returns the number of components
      inline std::size_t size() const {
        return (m_components->size());
      }
  
      // Beginning iterator for component indices
      iterator begin() const {
        return (iterator(0));
      }
  
      // End iterator for component indices
      iterator end() const {
        return (iterator(this->size()));
      }
  
      // Returns a pair of begin and end iterators for the child
      // elements of component [component_index].
      std::pair<component_iterator, component_iterator>
      operator[](IndexType component_index) const {
  
        IndexType first_index = (*m_components)[component_index];
  
        return (std::make_pair
                (component_iterator(m_index_list->begin(), first_index),
                 component_iterator(m_num_elements)));
      }
  
    private:
      template <typename ParentIterator,
                typename ElementIndexMap>
      void build_index_lists(ParentIterator parent_start,
                             const ElementIndexMap& index_map) {
  
        typedef typename std::iterator_traits<ParentIterator>::value_type Element;
        typename IndexContainer::iterator index_list =
          m_index_list->begin();
  
        // First pass - find root elements, construct index list
        for (IndexType element_index = 0; element_index < m_num_elements;
             ++element_index) {
  
          Element parent_element = parent_start[element_index];
          IndexType parent_index = get(index_map, parent_element);
  
          if (element_index != parent_index) {
            index_list[element_index] = parent_index;
          }
          else {
            m_components->push_back(element_index);
  
            // m_num_elements is the linked list terminator
            index_list[element_index] = m_num_elements;
          }
        }
  
        // Second pass - build linked list
        for (IndexType element_index = 0; element_index < m_num_elements;
             ++element_index) {
  
          Element parent_element = parent_start[element_index];
          IndexType parent_index = get(index_map, parent_element);
  
          if (element_index != parent_index) {
  
            // Follow list until a component parent is found
            while (index_list[parent_index] != m_num_elements) {
              parent_index = index_list[parent_index];
            }
  
            // Push element to the front of the linked list
            index_list[element_index] = index_list[parent_index];
            index_list[parent_index] = element_index;
          }
        }
  
      } // build_index_lists
  
    protected:
      IndexType m_num_elements;
      shared_ptr<IndexContainer> m_components, m_index_list;
  
    }; // class component_index
   
  } // namespace boost
  
  #endif // BOOST_INCREMENTAL_COMPONENTS_HPP
  