epoc32/include/stdapis/boost/graph/incremental_components.hpp
branchSymbian2
changeset 2 2fe1408b6811
     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