| // |
| //======================================================================= |
| // 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 |