diff -r 2fe1408b6811 -r e1b950c65cb4 epoc32/include/stdapis/boost/graph/incremental_components.hpp --- a/epoc32/include/stdapis/boost/graph/incremental_components.hpp Tue Mar 16 16:12:26 2010 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,170 +0,0 @@ -// -//======================================================================= -// 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