1.1 --- a/epoc32/include/stdapis/boost/graph/detail/incremental_components.hpp Wed Mar 31 12:27:01 2010 +0100
1.2 +++ b/epoc32/include/stdapis/boost/graph/detail/incremental_components.hpp Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -1,170 +1,141 @@
1.4 -//
1.5 //=======================================================================
1.6 -// Copyright 1997-2001 University of Notre Dame.
1.7 +// Copyright 2002 Indiana University.
1.8 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.9 //
1.10 // Distributed under the Boost Software License, Version 1.0. (See
1.11 // accompanying file LICENSE_1_0.txt or copy at
1.12 // http://www.boost.org/LICENSE_1_0.txt)
1.13 //=======================================================================
1.14 -//
1.15
1.16 -#ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
1.17 -#define BOOST_INCREMENTAL_COMPONENTS_HPP
1.18 +#ifndef BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
1.19 +#define BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
1.20
1.21 -#include <boost/detail/iterator.hpp>
1.22 -#include <boost/graph/detail/incremental_components.hpp>
1.23 +#include <boost/operators.hpp>
1.24 +#include <boost/pending/disjoint_sets.hpp>
1.25
1.26 namespace boost {
1.27
1.28 - // A connected component algorithm for the case when dynamically
1.29 - // adding (but not removing) edges is common. The
1.30 - // incremental_components() function is a preparing operation. Call
1.31 - // same_component to check whether two vertices are in the same
1.32 - // component, or use disjoint_set::find_set to determine the
1.33 - // representative for a vertex.
1.34 + namespace detail {
1.35
1.36 - // This version of connected components does not require a full
1.37 - // Graph. Instead, it just needs an edge list, where the vertices of
1.38 - // each edge need to be of integer type. The edges are assumed to
1.39 - // be undirected. The other difference is that the result is stored in
1.40 - // a container, instead of just a decorator. The container should be
1.41 - // empty before the algorithm is called. It will grow during the
1.42 - // course of the algorithm. The container must be a model of
1.43 - // BackInsertionSequence and RandomAccessContainer
1.44 - // (std::vector is a good choice). After running the algorithm the
1.45 - // index container will map each vertex to the representative
1.46 - // vertex of the component to which it belongs.
1.47 - //
1.48 - // Adapted from an implementation by Alex Stepanov. The disjoint
1.49 - // sets data structure is from Tarjan's "Data Structures and Network
1.50 - // Algorithms", and the application to connected components is
1.51 - // similar to the algorithm described in Ch. 22 of "Intro to
1.52 - // Algorithms" by Cormen, et. all.
1.53 - //
1.54 - // RankContainer is a random accessable container (operator[] is
1.55 - // defined) with a value type that can represent an integer part of
1.56 - // a binary log of the value type of the corresponding
1.57 - // ParentContainer (char is always enough) its size_type is no less
1.58 - // than the size_type of the corresponding ParentContainer
1.59 + //=========================================================================
1.60 + // Implementation detail of incremental_components
1.61
1.62 - // An implementation of disjoint sets can be found in
1.63 - // boost/pending/disjoint_sets.hpp
1.64 -
1.65 - template <class EdgeListGraph, class DisjointSets>
1.66 - void incremental_components(EdgeListGraph& g, DisjointSets& ds)
1.67 - {
1.68 - typename graph_traits<EdgeListGraph>::edge_iterator e, end;
1.69 - for (tie(e,end) = edges(g); e != end; ++e)
1.70 - ds.union_set(source(*e,g),target(*e,g));
1.71 - }
1.72 -
1.73 - template <class ParentIterator>
1.74 - void compress_components(ParentIterator first, ParentIterator last)
1.75 - {
1.76 - for (ParentIterator current = first; current != last; ++current)
1.77 - detail::find_representative_with_full_compression(first, current-first);
1.78 - }
1.79 -
1.80 - template <class ParentIterator>
1.81 - typename boost::detail::iterator_traits<ParentIterator>::difference_type
1.82 - component_count(ParentIterator first, ParentIterator last)
1.83 - {
1.84 - std::ptrdiff_t count = 0;
1.85 - for (ParentIterator current = first; current != last; ++current)
1.86 - if (*current == current - first) ++count;
1.87 - return count;
1.88 - }
1.89 -
1.90 - // This algorithm can be applied to the result container of the
1.91 - // connected_components algorithm to normalize
1.92 - // the components.
1.93 - template <class ParentIterator>
1.94 - void normalize_components(ParentIterator first, ParentIterator last)
1.95 - {
1.96 - for (ParentIterator current = first; current != last; ++current)
1.97 - detail::normalize_node(first, current - first);
1.98 - }
1.99 -
1.100 - template <class VertexListGraph, class DisjointSets>
1.101 - void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
1.102 - {
1.103 - typename graph_traits<VertexListGraph>
1.104 - ::vertex_iterator v, vend;
1.105 - for (tie(v, vend) = vertices(G); v != vend; ++v)
1.106 - ds.make_set(*v);
1.107 - }
1.108
1.109 - template <class Vertex, class DisjointSet>
1.110 - inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
1.111 - {
1.112 - return ds.find_set(u) == ds.find_set(v);
1.113 - }
1.114 + //-------------------------------------------------------------------------
1.115 + // Helper functions for the component_index class
1.116 +
1.117 + // Record the representative vertices in the header array.
1.118 + // Representative vertices now point to the component number.
1.119 +
1.120 + template <class Parent, class OutputIterator, class Integer>
1.121 + inline void
1.122 + build_components_header(Parent p,
1.123 + OutputIterator header,
1.124 + Integer num_nodes)
1.125 + {
1.126 + Parent component = p;
1.127 + Integer component_num = 0;
1.128 + for (Integer v = 0; v != num_nodes; ++v)
1.129 + if (p[v] == v) {
1.130 + *header++ = v;
1.131 + component[v] = component_num++;
1.132 + }
1.133 + }
1.134 +
1.135 +
1.136 + // Pushes x onto the front of the list. The list is represented in
1.137 + // an array.
1.138 + template <class Next, class T, class V>
1.139 + inline void array_push_front(Next next, T& head, V x)
1.140 + {
1.141 + T tmp = head;
1.142 + head = x;
1.143 + next[x] = tmp;
1.144 + }
1.145 +
1.146 +
1.147 + // Create a linked list of the vertices in each component
1.148 + // by reusing the representative array.
1.149 + template <class Parent1, class Parent2,
1.150 + class Integer>
1.151 + void
1.152 + link_components(Parent1 component, Parent2 header,
1.153 + Integer num_nodes, Integer num_components)
1.154 + {
1.155 + // Make the non-representative vertices point to their component
1.156 + Parent1 representative = component;
1.157 + for (Integer v = 0; v != num_nodes; ++v)
1.158 + if (component[v] >= num_components
1.159 + || header[component[v]] != v)
1.160 + component[v] = component[representative[v]];
1.161 +
1.162 + // initialize the "head" of the lists to "NULL"
1.163 + std::fill_n(header, num_components, num_nodes);
1.164 +
1.165 + // Add each vertex to the linked list for its component
1.166 + Parent1 next = component;
1.167 + for (Integer k = 0; k != num_nodes; ++k)
1.168 + array_push_front(next, header[component[k]], k);
1.169 + }
1.170 +
1.171
1.172 - // considering changing the so that it initializes with a pair of
1.173 - // vertex iterators and a parent PA.
1.174 -
1.175 - template <class IndexT>
1.176 - class component_index
1.177 - {
1.178 - public://protected: (avoid friends for now)
1.179 - typedef std::vector<IndexT> MyIndexContainer;
1.180 - MyIndexContainer header;
1.181 - MyIndexContainer index;
1.182 - typedef typename MyIndexContainer::size_type SizeT;
1.183 - typedef typename MyIndexContainer::const_iterator IndexIter;
1.184 - public:
1.185 - typedef detail::component_iterator<IndexIter, IndexT, SizeT>
1.186 - component_iterator;
1.187 - class component {
1.188 - friend class component_index;
1.189 - protected:
1.190 - IndexT number;
1.191 - const component_index<IndexT>* comp_ind_ptr;
1.192 - component(IndexT i, const component_index<IndexT>* p)
1.193 - : number(i), comp_ind_ptr(p) {}
1.194 +
1.195 + template <class IndexContainer, class HeaderContainer>
1.196 + void
1.197 + construct_component_index(IndexContainer& index, HeaderContainer& header)
1.198 + {
1.199 + typedef typename IndexContainer::value_type Integer;
1.200 + build_components_header(index.begin(),
1.201 + std::back_inserter(header),
1.202 + Integer(index.end() - index.begin()));
1.203 +
1.204 + link_components(index.begin(), header.begin(),
1.205 + Integer(index.end() - index.begin()),
1.206 + Integer(header.end() - header.begin()));
1.207 + }
1.208 +
1.209 +
1.210 +
1.211 + template <class IndexIterator, class Integer, class Distance>
1.212 + class component_iterator
1.213 + : boost::forward_iterator_helper<
1.214 + component_iterator<IndexIterator,Integer,Distance>,
1.215 + Integer, Distance,Integer*, Integer&>
1.216 + {
1.217 public:
1.218 - typedef component_iterator iterator;
1.219 - typedef component_iterator const_iterator;
1.220 - typedef IndexT value_type;
1.221 - iterator begin() const {
1.222 - return iterator( comp_ind_ptr->index.begin(),
1.223 - (comp_ind_ptr->header)[number] );
1.224 + typedef component_iterator self;
1.225 +
1.226 + IndexIterator next;
1.227 + Integer node;
1.228 +
1.229 + typedef std::forward_iterator_tag iterator_category;
1.230 + typedef Integer value_type;
1.231 + typedef Integer& reference;
1.232 + typedef Integer* pointer;
1.233 + typedef Distance difference_type;
1.234 +
1.235 + component_iterator() {}
1.236 + component_iterator(IndexIterator x, Integer i)
1.237 + : next(x), node(i) {}
1.238 + Integer operator*() const {
1.239 + return node;
1.240 }
1.241 - iterator end() const {
1.242 - return iterator( comp_ind_ptr->index.begin(),
1.243 - comp_ind_ptr->index.size() );
1.244 + self& operator++() {
1.245 + node = next[node];
1.246 + return *this;
1.247 }
1.248 };
1.249 - typedef SizeT size_type;
1.250 - typedef component value_type;
1.251
1.252 -#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
1.253 - template <class Iterator>
1.254 - component_index(Iterator first, Iterator last)
1.255 - : index(std::distance(first, last))
1.256 - {
1.257 - std::copy(first, last, index.begin());
1.258 - detail::construct_component_index(index, header);
1.259 + template <class IndexIterator, class Integer, class Distance>
1.260 + inline bool
1.261 + operator==(const component_iterator<IndexIterator, Integer, Distance>& x,
1.262 + const component_iterator<IndexIterator, Integer, Distance>& y)
1.263 + {
1.264 + return x.node == y.node;
1.265 }
1.266 -#else
1.267 - template <class Iterator>
1.268 - component_index(Iterator first, Iterator last)
1.269 - : index(first, last)
1.270 - {
1.271 - detail::construct_component_index(index, header);
1.272 - }
1.273 -#endif
1.274 +
1.275 + } // namespace detail
1.276 +
1.277 +} // namespace detail
1.278
1.279 - component operator[](IndexT i) const {
1.280 - return component(i, this);
1.281 - }
1.282 - SizeT size() const {
1.283 - return header.size();
1.284 - }
1.285 -
1.286 - };
1.287 -
1.288 -} // namespace boost
1.289 -
1.290 -#endif // BOOST_INCREMENTAL_COMPONENTS_HPP
1.291 +#endif // BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP