diff -r 000000000000 -r bde4ae8d615e os/ossrv/ossrv_pub/boost_apis/boost/graph/incremental_components.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/graph/incremental_components.hpp Fri Jun 15 03:10:57 2012 +0200 @@ -0,0 +1,170 @@ +// +//======================================================================= +// Copyright 1997-2001 University of Notre Dame. +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek +// +// 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 +#include + +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. + // + // RankContainer is a random accessable container (operator[] is + // defined) with a value type that can represent an integer part of + // a binary log of the value type of the corresponding + // ParentContainer (char is always enough) its size_type is no less + // than the size_type of the corresponding ParentContainer + + // An implementation of disjoint sets can be found in + // boost/pending/disjoint_sets.hpp + + template + void incremental_components(EdgeListGraph& g, DisjointSets& ds) + { + typename graph_traits::edge_iterator e, end; + for (tie(e,end) = edges(g); e != end; ++e) + ds.union_set(source(*e,g),target(*e,g)); + } + + template + void compress_components(ParentIterator first, ParentIterator last) + { + for (ParentIterator current = first; current != last; ++current) + detail::find_representative_with_full_compression(first, current-first); + } + + template + typename boost::detail::iterator_traits::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 + void normalize_components(ParentIterator first, ParentIterator last) + { + for (ParentIterator current = first; current != last; ++current) + detail::normalize_node(first, current - first); + } + + template + void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds) + { + typename graph_traits + ::vertex_iterator v, vend; + for (tie(v, vend) = vertices(G); v != vend; ++v) + ds.make_set(*v); + } + + template + inline bool same_component(Vertex u, Vertex v, DisjointSet& ds) + { + return ds.find_set(u) == ds.find_set(v); + } + + // considering changing the so that it initializes with a pair of + // vertex iterators and a parent PA. + + template + class component_index + { + public://protected: (avoid friends for now) + typedef std::vector MyIndexContainer; + MyIndexContainer header; + MyIndexContainer index; + typedef typename MyIndexContainer::size_type SizeT; + typedef typename MyIndexContainer::const_iterator IndexIter; + public: + typedef detail::component_iterator + component_iterator; + class component { + friend class component_index; + protected: + IndexT number; + const component_index* comp_ind_ptr; + component(IndexT i, const component_index* p) + : number(i), comp_ind_ptr(p) {} + public: + typedef component_iterator iterator; + typedef component_iterator const_iterator; + typedef IndexT value_type; + iterator begin() const { + return iterator( comp_ind_ptr->index.begin(), + (comp_ind_ptr->header)[number] ); + } + iterator end() const { + return iterator( comp_ind_ptr->index.begin(), + comp_ind_ptr->index.size() ); + } + }; + typedef SizeT size_type; + typedef component value_type; + +#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS) + template + component_index(Iterator first, Iterator last) + : index(std::distance(first, last)) + { + std::copy(first, last, index.begin()); + detail::construct_component_index(index, header); + } +#else + template + component_index(Iterator first, Iterator last) + : index(first, last) + { + detail::construct_component_index(index, header); + } +#endif + + component operator[](IndexT i) const { + return component(i, this); + } + SizeT size() const { + return header.size(); + } + + }; + +} // namespace boost + +#endif // BOOST_INCREMENTAL_COMPONENTS_HPP