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