1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/incremental_components.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,170 @@
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