1.1 --- a/epoc32/include/stdapis/boost/graph/incremental_components.hpp Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,170 +0,0 @@
1.4 -//
1.5 -//=======================================================================
1.6 -// Copyright 1997-2001 University of Notre Dame.
1.7 -// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 -//
1.9 -// Distributed under the Boost Software License, Version 1.0. (See
1.10 -// accompanying file LICENSE_1_0.txt or copy at
1.11 -// http://www.boost.org/LICENSE_1_0.txt)
1.12 -//=======================================================================
1.13 -//
1.14 -
1.15 -#ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
1.16 -#define BOOST_INCREMENTAL_COMPONENTS_HPP
1.17 -
1.18 -#include <boost/detail/iterator.hpp>
1.19 -#include <boost/graph/detail/incremental_components.hpp>
1.20 -
1.21 -namespace boost {
1.22 -
1.23 - // A connected component algorithm for the case when dynamically
1.24 - // adding (but not removing) edges is common. The
1.25 - // incremental_components() function is a preparing operation. Call
1.26 - // same_component to check whether two vertices are in the same
1.27 - // component, or use disjoint_set::find_set to determine the
1.28 - // representative for a vertex.
1.29 -
1.30 - // This version of connected components does not require a full
1.31 - // Graph. Instead, it just needs an edge list, where the vertices of
1.32 - // each edge need to be of integer type. The edges are assumed to
1.33 - // be undirected. The other difference is that the result is stored in
1.34 - // a container, instead of just a decorator. The container should be
1.35 - // empty before the algorithm is called. It will grow during the
1.36 - // course of the algorithm. The container must be a model of
1.37 - // BackInsertionSequence and RandomAccessContainer
1.38 - // (std::vector is a good choice). After running the algorithm the
1.39 - // index container will map each vertex to the representative
1.40 - // vertex of the component to which it belongs.
1.41 - //
1.42 - // Adapted from an implementation by Alex Stepanov. The disjoint
1.43 - // sets data structure is from Tarjan's "Data Structures and Network
1.44 - // Algorithms", and the application to connected components is
1.45 - // similar to the algorithm described in Ch. 22 of "Intro to
1.46 - // Algorithms" by Cormen, et. all.
1.47 - //
1.48 - // RankContainer is a random accessable container (operator[] is
1.49 - // defined) with a value type that can represent an integer part of
1.50 - // a binary log of the value type of the corresponding
1.51 - // ParentContainer (char is always enough) its size_type is no less
1.52 - // than the size_type of the corresponding ParentContainer
1.53 -
1.54 - // An implementation of disjoint sets can be found in
1.55 - // boost/pending/disjoint_sets.hpp
1.56 -
1.57 - template <class EdgeListGraph, class DisjointSets>
1.58 - void incremental_components(EdgeListGraph& g, DisjointSets& ds)
1.59 - {
1.60 - typename graph_traits<EdgeListGraph>::edge_iterator e, end;
1.61 - for (tie(e,end) = edges(g); e != end; ++e)
1.62 - ds.union_set(source(*e,g),target(*e,g));
1.63 - }
1.64 -
1.65 - template <class ParentIterator>
1.66 - void compress_components(ParentIterator first, ParentIterator last)
1.67 - {
1.68 - for (ParentIterator current = first; current != last; ++current)
1.69 - detail::find_representative_with_full_compression(first, current-first);
1.70 - }
1.71 -
1.72 - template <class ParentIterator>
1.73 - typename boost::detail::iterator_traits<ParentIterator>::difference_type
1.74 - component_count(ParentIterator first, ParentIterator last)
1.75 - {
1.76 - std::ptrdiff_t count = 0;
1.77 - for (ParentIterator current = first; current != last; ++current)
1.78 - if (*current == current - first) ++count;
1.79 - return count;
1.80 - }
1.81 -
1.82 - // This algorithm can be applied to the result container of the
1.83 - // connected_components algorithm to normalize
1.84 - // the components.
1.85 - template <class ParentIterator>
1.86 - void normalize_components(ParentIterator first, ParentIterator last)
1.87 - {
1.88 - for (ParentIterator current = first; current != last; ++current)
1.89 - detail::normalize_node(first, current - first);
1.90 - }
1.91 -
1.92 - template <class VertexListGraph, class DisjointSets>
1.93 - void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
1.94 - {
1.95 - typename graph_traits<VertexListGraph>
1.96 - ::vertex_iterator v, vend;
1.97 - for (tie(v, vend) = vertices(G); v != vend; ++v)
1.98 - ds.make_set(*v);
1.99 - }
1.100 -
1.101 - template <class Vertex, class DisjointSet>
1.102 - inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
1.103 - {
1.104 - return ds.find_set(u) == ds.find_set(v);
1.105 - }
1.106 -
1.107 - // considering changing the so that it initializes with a pair of
1.108 - // vertex iterators and a parent PA.
1.109 -
1.110 - template <class IndexT>
1.111 - class component_index
1.112 - {
1.113 - public://protected: (avoid friends for now)
1.114 - typedef std::vector<IndexT> MyIndexContainer;
1.115 - MyIndexContainer header;
1.116 - MyIndexContainer index;
1.117 - typedef typename MyIndexContainer::size_type SizeT;
1.118 - typedef typename MyIndexContainer::const_iterator IndexIter;
1.119 - public:
1.120 - typedef detail::component_iterator<IndexIter, IndexT, SizeT>
1.121 - component_iterator;
1.122 - class component {
1.123 - friend class component_index;
1.124 - protected:
1.125 - IndexT number;
1.126 - const component_index<IndexT>* comp_ind_ptr;
1.127 - component(IndexT i, const component_index<IndexT>* p)
1.128 - : number(i), comp_ind_ptr(p) {}
1.129 - public:
1.130 - typedef component_iterator iterator;
1.131 - typedef component_iterator const_iterator;
1.132 - typedef IndexT value_type;
1.133 - iterator begin() const {
1.134 - return iterator( comp_ind_ptr->index.begin(),
1.135 - (comp_ind_ptr->header)[number] );
1.136 - }
1.137 - iterator end() const {
1.138 - return iterator( comp_ind_ptr->index.begin(),
1.139 - comp_ind_ptr->index.size() );
1.140 - }
1.141 - };
1.142 - typedef SizeT size_type;
1.143 - typedef component value_type;
1.144 -
1.145 -#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
1.146 - template <class Iterator>
1.147 - component_index(Iterator first, Iterator last)
1.148 - : index(std::distance(first, last))
1.149 - {
1.150 - std::copy(first, last, index.begin());
1.151 - detail::construct_component_index(index, header);
1.152 - }
1.153 -#else
1.154 - template <class Iterator>
1.155 - component_index(Iterator first, Iterator last)
1.156 - : index(first, last)
1.157 - {
1.158 - detail::construct_component_index(index, header);
1.159 - }
1.160 -#endif
1.161 -
1.162 - component operator[](IndexT i) const {
1.163 - return component(i, this);
1.164 - }
1.165 - SizeT size() const {
1.166 - return header.size();
1.167 - }
1.168 -
1.169 - };
1.170 -
1.171 -} // namespace boost
1.172 -
1.173 -#endif // BOOST_INCREMENTAL_COMPONENTS_HPP