williamr@2: // williamr@2: //======================================================================= williamr@2: // Copyright 1997-2001 University of Notre Dame. williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: //======================================================================= williamr@2: // williamr@2: williamr@2: #ifndef BOOST_INCREMENTAL_COMPONENTS_HPP williamr@2: #define BOOST_INCREMENTAL_COMPONENTS_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: // A connected component algorithm for the case when dynamically williamr@2: // adding (but not removing) edges is common. The williamr@2: // incremental_components() function is a preparing operation. Call williamr@2: // same_component to check whether two vertices are in the same williamr@2: // component, or use disjoint_set::find_set to determine the williamr@2: // representative for a vertex. williamr@2: williamr@2: // This version of connected components does not require a full williamr@2: // Graph. Instead, it just needs an edge list, where the vertices of williamr@2: // each edge need to be of integer type. The edges are assumed to williamr@2: // be undirected. The other difference is that the result is stored in williamr@2: // a container, instead of just a decorator. The container should be williamr@2: // empty before the algorithm is called. It will grow during the williamr@2: // course of the algorithm. The container must be a model of williamr@2: // BackInsertionSequence and RandomAccessContainer williamr@2: // (std::vector is a good choice). After running the algorithm the williamr@2: // index container will map each vertex to the representative williamr@2: // vertex of the component to which it belongs. williamr@2: // williamr@2: // Adapted from an implementation by Alex Stepanov. The disjoint williamr@2: // sets data structure is from Tarjan's "Data Structures and Network williamr@2: // Algorithms", and the application to connected components is williamr@2: // similar to the algorithm described in Ch. 22 of "Intro to williamr@2: // Algorithms" by Cormen, et. all. williamr@2: // williamr@2: // RankContainer is a random accessable container (operator[] is williamr@2: // defined) with a value type that can represent an integer part of williamr@2: // a binary log of the value type of the corresponding williamr@2: // ParentContainer (char is always enough) its size_type is no less williamr@2: // than the size_type of the corresponding ParentContainer williamr@2: williamr@2: // An implementation of disjoint sets can be found in williamr@2: // boost/pending/disjoint_sets.hpp williamr@2: williamr@2: template williamr@2: void incremental_components(EdgeListGraph& g, DisjointSets& ds) williamr@2: { williamr@2: typename graph_traits::edge_iterator e, end; williamr@2: for (tie(e,end) = edges(g); e != end; ++e) williamr@2: ds.union_set(source(*e,g),target(*e,g)); williamr@2: } williamr@2: williamr@2: template williamr@2: void compress_components(ParentIterator first, ParentIterator last) williamr@2: { williamr@2: for (ParentIterator current = first; current != last; ++current) williamr@2: detail::find_representative_with_full_compression(first, current-first); williamr@2: } williamr@2: williamr@2: template williamr@2: typename boost::detail::iterator_traits::difference_type williamr@2: component_count(ParentIterator first, ParentIterator last) williamr@2: { williamr@2: std::ptrdiff_t count = 0; williamr@2: for (ParentIterator current = first; current != last; ++current) williamr@2: if (*current == current - first) ++count; williamr@2: return count; williamr@2: } williamr@2: williamr@2: // This algorithm can be applied to the result container of the williamr@2: // connected_components algorithm to normalize williamr@2: // the components. williamr@2: template williamr@2: void normalize_components(ParentIterator first, ParentIterator last) williamr@2: { williamr@2: for (ParentIterator current = first; current != last; ++current) williamr@2: detail::normalize_node(first, current - first); williamr@2: } williamr@2: williamr@2: template williamr@2: void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds) williamr@2: { williamr@2: typename graph_traits williamr@2: ::vertex_iterator v, vend; williamr@2: for (tie(v, vend) = vertices(G); v != vend; ++v) williamr@2: ds.make_set(*v); williamr@2: } williamr@2: williamr@2: template williamr@2: inline bool same_component(Vertex u, Vertex v, DisjointSet& ds) williamr@2: { williamr@2: return ds.find_set(u) == ds.find_set(v); williamr@2: } williamr@2: williamr@2: // considering changing the so that it initializes with a pair of williamr@2: // vertex iterators and a parent PA. williamr@2: williamr@2: template williamr@2: class component_index williamr@2: { williamr@2: public://protected: (avoid friends for now) williamr@2: typedef std::vector MyIndexContainer; williamr@2: MyIndexContainer header; williamr@2: MyIndexContainer index; williamr@2: typedef typename MyIndexContainer::size_type SizeT; williamr@2: typedef typename MyIndexContainer::const_iterator IndexIter; williamr@2: public: williamr@2: typedef detail::component_iterator williamr@2: component_iterator; williamr@2: class component { williamr@2: friend class component_index; williamr@2: protected: williamr@2: IndexT number; williamr@2: const component_index* comp_ind_ptr; williamr@2: component(IndexT i, const component_index* p) williamr@2: : number(i), comp_ind_ptr(p) {} williamr@2: public: williamr@2: typedef component_iterator iterator; williamr@2: typedef component_iterator const_iterator; williamr@2: typedef IndexT value_type; williamr@2: iterator begin() const { williamr@2: return iterator( comp_ind_ptr->index.begin(), williamr@2: (comp_ind_ptr->header)[number] ); williamr@2: } williamr@2: iterator end() const { williamr@2: return iterator( comp_ind_ptr->index.begin(), williamr@2: comp_ind_ptr->index.size() ); williamr@2: } williamr@2: }; williamr@2: typedef SizeT size_type; williamr@2: typedef component value_type; williamr@2: williamr@2: #if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS) williamr@2: template williamr@2: component_index(Iterator first, Iterator last) williamr@2: : index(std::distance(first, last)) williamr@2: { williamr@2: std::copy(first, last, index.begin()); williamr@2: detail::construct_component_index(index, header); williamr@2: } williamr@2: #else williamr@2: template williamr@2: component_index(Iterator first, Iterator last) williamr@2: : index(first, last) williamr@2: { williamr@2: detail::construct_component_index(index, header); williamr@2: } williamr@2: #endif williamr@2: williamr@2: component operator[](IndexT i) const { williamr@2: return component(i, this); williamr@2: } williamr@2: SizeT size() const { williamr@2: return header.size(); williamr@2: } williamr@2: williamr@2: }; williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #endif // BOOST_INCREMENTAL_COMPONENTS_HPP