Chris@16: //
Chris@16: //=======================================================================
Chris@16: // Copyright 1997-2001 University of Notre Dame.
Chris@16: // Copyright 2009 Trustees of Indiana University.
Chris@16: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: 
Chris@16: #ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
Chris@16: #define BOOST_INCREMENTAL_COMPONENTS_HPP
Chris@16: 
Chris@16: #include <boost/detail/iterator.hpp>
Chris@16: #include <boost/graph/detail/incremental_components.hpp>
Chris@16: #include <boost/iterator/counting_iterator.hpp>
Chris@16: #include <boost/make_shared.hpp>
Chris@16: #include <boost/pending/disjoint_sets.hpp>
Chris@16: #include <iterator>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   // A connected component algorithm for the case when dynamically
Chris@16:   // adding (but not removing) edges is common.  The
Chris@16:   // incremental_components() function is a preparing operation. Call
Chris@16:   // same_component to check whether two vertices are in the same
Chris@16:   // component, or use disjoint_set::find_set to determine the
Chris@16:   // representative for a vertex.
Chris@16: 
Chris@16:   // This version of connected components does not require a full
Chris@16:   // Graph. Instead, it just needs an edge list, where the vertices of
Chris@16:   // each edge need to be of integer type. The edges are assumed to
Chris@16:   // be undirected. The other difference is that the result is stored in
Chris@16:   // a container, instead of just a decorator.  The container should be
Chris@16:   // empty before the algorithm is called. It will grow during the
Chris@16:   // course of the algorithm. The container must be a model of
Chris@16:   // BackInsertionSequence and RandomAccessContainer
Chris@16:   // (std::vector is a good choice). After running the algorithm the
Chris@16:   // index container will map each vertex to the representative
Chris@16:   // vertex of the component to which it belongs.
Chris@16:   //
Chris@16:   // Adapted from an implementation by Alex Stepanov. The disjoint
Chris@16:   // sets data structure is from Tarjan's "Data Structures and Network
Chris@16:   // Algorithms", and the application to connected components is
Chris@16:   // similar to the algorithm described in Ch. 22 of "Intro to
Chris@16:   // Algorithms" by Cormen, et. all.
Chris@16:   //  
Chris@16: 
Chris@16:   // An implementation of disjoint sets can be found in
Chris@16:   // boost/pending/disjoint_sets.hpp
Chris@16:   
Chris@16:   template <class EdgeListGraph, class DisjointSets>
Chris@16:   void incremental_components(EdgeListGraph& g, DisjointSets& ds)
Chris@16:   {
Chris@16:     typename graph_traits<EdgeListGraph>::edge_iterator e, end;
Chris@16:     for (boost::tie(e,end) = edges(g); e != end; ++e)
Chris@16:       ds.union_set(source(*e,g),target(*e,g));
Chris@16:   }
Chris@16:   
Chris@16:   template <class ParentIterator>
Chris@16:   void compress_components(ParentIterator first, ParentIterator last)
Chris@16:   {
Chris@16:     for (ParentIterator current = first; current != last; ++current) 
Chris@16:       detail::find_representative_with_full_compression(first, current-first);
Chris@16:   }
Chris@16:   
Chris@16:   template <class ParentIterator>
Chris@16:   typename boost::detail::iterator_traits<ParentIterator>::difference_type
Chris@16:   component_count(ParentIterator first, ParentIterator last)
Chris@16:   {
Chris@16:     std::ptrdiff_t count = 0;
Chris@16:     for (ParentIterator current = first; current != last; ++current) 
Chris@16:       if (*current == current - first) ++count; 
Chris@16:     return count;
Chris@16:   }
Chris@16:   
Chris@16:   // This algorithm can be applied to the result container of the
Chris@16:   // connected_components algorithm to normalize
Chris@16:   // the components.
Chris@16:   template <class ParentIterator>
Chris@16:   void normalize_components(ParentIterator first, ParentIterator last)
Chris@16:   {
Chris@16:     for (ParentIterator current = first; current != last; ++current) 
Chris@16:       detail::normalize_node(first, current - first);
Chris@16:   }
Chris@16:   
Chris@16:   template <class VertexListGraph, class DisjointSets> 
Chris@16:   void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
Chris@16:   {
Chris@16:     typename graph_traits<VertexListGraph>
Chris@16:       ::vertex_iterator v, vend;
Chris@16:     for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
Chris@16:       ds.make_set(*v);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Vertex, class DisjointSet>
Chris@16:   inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
Chris@16:   {
Chris@16:     return ds.find_set(u) == ds.find_set(v);
Chris@16:   }
Chris@16: 
Chris@16:   // Class that builds a quick-access indexed linked list that allows
Chris@16:   // for fast iterating through a parent component's children.
Chris@16:   template <typename IndexType>
Chris@16:   class component_index {
Chris@16: 
Chris@16:   private:
Chris@16:     typedef std::vector<IndexType> IndexContainer;
Chris@16: 
Chris@16:   public:
Chris@16:     typedef counting_iterator<IndexType> iterator;
Chris@16:     typedef iterator const_iterator;
Chris@16:     typedef IndexType value_type;
Chris@16:     typedef IndexType size_type;
Chris@16: 
Chris@16:     typedef detail::component_index_iterator<typename IndexContainer::iterator>
Chris@16:       component_iterator;
Chris@16: 
Chris@16:   public:
Chris@16:     template <typename ParentIterator,
Chris@16:               typename ElementIndexMap>
Chris@16:     component_index(ParentIterator parent_start,
Chris@16:                     ParentIterator parent_end,
Chris@16:                     const ElementIndexMap& index_map) :
Chris@16:       m_num_elements(std::distance(parent_start, parent_end)),
Chris@16:       m_components(make_shared<IndexContainer>()),
Chris@16:       m_index_list(make_shared<IndexContainer>(m_num_elements)) {
Chris@16: 
Chris@16:       build_index_lists(parent_start, index_map);
Chris@16:       
Chris@16:     } // component_index
Chris@16: 
Chris@16:     template <typename ParentIterator>
Chris@16:     component_index(ParentIterator parent_start,
Chris@16:                     ParentIterator parent_end) :
Chris@16:       m_num_elements(std::distance(parent_start, parent_end)),
Chris@16:       m_components(make_shared<IndexContainer>()),
Chris@16:       m_index_list(make_shared<IndexContainer>(m_num_elements)) {
Chris@16: 
Chris@16:       build_index_lists(parent_start, boost::identity_property_map());
Chris@16: 
Chris@16:     } // component_index
Chris@16: 
Chris@16:     // Returns the number of components
Chris@16:     inline std::size_t size() const {
Chris@16:       return (m_components->size());
Chris@16:     }
Chris@16: 
Chris@16:     // Beginning iterator for component indices
Chris@16:     iterator begin() const {
Chris@16:       return (iterator(0));
Chris@16:     }
Chris@16: 
Chris@16:     // End iterator for component indices
Chris@16:     iterator end() const {
Chris@16:       return (iterator(this->size()));
Chris@16:     }
Chris@16: 
Chris@16:     // Returns a pair of begin and end iterators for the child
Chris@16:     // elements of component [component_index].
Chris@16:     std::pair<component_iterator, component_iterator>
Chris@16:     operator[](IndexType component_index) const {
Chris@16: 
Chris@16:       IndexType first_index = (*m_components)[component_index];
Chris@16: 
Chris@16:       return (std::make_pair
Chris@16:               (component_iterator(m_index_list->begin(), first_index),
Chris@16:                component_iterator(m_num_elements)));
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16:     template <typename ParentIterator,
Chris@16:               typename ElementIndexMap>
Chris@16:     void build_index_lists(ParentIterator parent_start,
Chris@16:                            const ElementIndexMap& index_map) {
Chris@16: 
Chris@16:       typedef typename std::iterator_traits<ParentIterator>::value_type Element;
Chris@16:       typename IndexContainer::iterator index_list =
Chris@16:         m_index_list->begin();
Chris@16: 
Chris@16:       // First pass - find root elements, construct index list
Chris@16:       for (IndexType element_index = 0; element_index < m_num_elements;
Chris@16:            ++element_index) {
Chris@16: 
Chris@16:         Element parent_element = parent_start[element_index];
Chris@16:         IndexType parent_index = get(index_map, parent_element);
Chris@16: 
Chris@16:         if (element_index != parent_index) {
Chris@16:           index_list[element_index] = parent_index;
Chris@16:         }
Chris@16:         else {
Chris@16:           m_components->push_back(element_index);
Chris@16: 
Chris@16:           // m_num_elements is the linked list terminator
Chris@16:           index_list[element_index] = m_num_elements;
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       // Second pass - build linked list
Chris@16:       for (IndexType element_index = 0; element_index < m_num_elements;
Chris@16:            ++element_index) {
Chris@16: 
Chris@16:         Element parent_element = parent_start[element_index];
Chris@16:         IndexType parent_index = get(index_map, parent_element);
Chris@16: 
Chris@16:         if (element_index != parent_index) {
Chris@16: 
Chris@16:           // Follow list until a component parent is found
Chris@16:           while (index_list[parent_index] != m_num_elements) {
Chris@16:             parent_index = index_list[parent_index];
Chris@16:           }
Chris@16: 
Chris@16:           // Push element to the front of the linked list
Chris@16:           index_list[element_index] = index_list[parent_index];
Chris@16:           index_list[parent_index] = element_index;
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:     } // build_index_lists
Chris@16: 
Chris@16:   protected:
Chris@16:     IndexType m_num_elements;
Chris@16:     shared_ptr<IndexContainer> m_components, m_index_list;
Chris@16: 
Chris@16:   }; // class component_index
Chris@16:  
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_INCREMENTAL_COMPONENTS_HPP