epoc32/include/stdapis/boost/graph/detail/incremental_components.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
parent 2 epoc32/include/stdapis/boost/graph/incremental_components.hpp@2fe1408b6811
child 4 837f303aceeb
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
     1 //
     2 //=======================================================================
     3 // Copyright 1997-2001 University of Notre Dame.
     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     5 //
     6 // Distributed under the Boost Software License, Version 1.0. (See
     7 // accompanying file LICENSE_1_0.txt or copy at
     8 // http://www.boost.org/LICENSE_1_0.txt)
     9 //=======================================================================
    10 //
    11 
    12 #ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
    13 #define BOOST_INCREMENTAL_COMPONENTS_HPP
    14 
    15 #include <boost/detail/iterator.hpp>
    16 #include <boost/graph/detail/incremental_components.hpp>
    17 
    18 namespace boost {
    19 
    20   // A connected component algorithm for the case when dynamically
    21   // adding (but not removing) edges is common.  The
    22   // incremental_components() function is a preparing operation. Call
    23   // same_component to check whether two vertices are in the same
    24   // component, or use disjoint_set::find_set to determine the
    25   // representative for a vertex.
    26 
    27   // This version of connected components does not require a full
    28   // Graph. Instead, it just needs an edge list, where the vertices of
    29   // each edge need to be of integer type. The edges are assumed to
    30   // be undirected. The other difference is that the result is stored in
    31   // a container, instead of just a decorator.  The container should be
    32   // empty before the algorithm is called. It will grow during the
    33   // course of the algorithm. The container must be a model of
    34   // BackInsertionSequence and RandomAccessContainer
    35   // (std::vector is a good choice). After running the algorithm the
    36   // index container will map each vertex to the representative
    37   // vertex of the component to which it belongs.
    38   //
    39   // Adapted from an implementation by Alex Stepanov. The disjoint
    40   // sets data structure is from Tarjan's "Data Structures and Network
    41   // Algorithms", and the application to connected components is
    42   // similar to the algorithm described in Ch. 22 of "Intro to
    43   // Algorithms" by Cormen, et. all.
    44   //  
    45   // RankContainer is a random accessable container (operator[] is
    46   // defined) with a value type that can represent an integer part of
    47   // a binary log of the value type of the corresponding
    48   // ParentContainer (char is always enough) its size_type is no less
    49   // than the size_type of the corresponding ParentContainer
    50 
    51   // An implementation of disjoint sets can be found in
    52   // boost/pending/disjoint_sets.hpp
    53   
    54   template <class EdgeListGraph, class DisjointSets>
    55   void incremental_components(EdgeListGraph& g, DisjointSets& ds)
    56   {
    57     typename graph_traits<EdgeListGraph>::edge_iterator e, end;
    58     for (tie(e,end) = edges(g); e != end; ++e)
    59       ds.union_set(source(*e,g),target(*e,g));
    60   }
    61   
    62   template <class ParentIterator>
    63   void compress_components(ParentIterator first, ParentIterator last)
    64   {
    65     for (ParentIterator current = first; current != last; ++current) 
    66       detail::find_representative_with_full_compression(first, current-first);
    67   }
    68   
    69   template <class ParentIterator>
    70   typename boost::detail::iterator_traits<ParentIterator>::difference_type
    71   component_count(ParentIterator first, ParentIterator last)
    72   {
    73     std::ptrdiff_t count = 0;
    74     for (ParentIterator current = first; current != last; ++current) 
    75       if (*current == current - first) ++count; 
    76     return count;
    77   }
    78   
    79   // This algorithm can be applied to the result container of the
    80   // connected_components algorithm to normalize
    81   // the components.
    82   template <class ParentIterator>
    83   void normalize_components(ParentIterator first, ParentIterator last)
    84   {
    85     for (ParentIterator current = first; current != last; ++current) 
    86       detail::normalize_node(first, current - first);
    87   }
    88   
    89   template <class VertexListGraph, class DisjointSets> 
    90   void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
    91   {
    92     typename graph_traits<VertexListGraph>
    93       ::vertex_iterator v, vend;
    94     for (tie(v, vend) = vertices(G); v != vend; ++v)
    95       ds.make_set(*v);
    96   }
    97 
    98   template <class Vertex, class DisjointSet>
    99   inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
   100   {
   101     return ds.find_set(u) == ds.find_set(v);
   102   }
   103 
   104   // considering changing the so that it initializes with a pair of
   105   // vertex iterators and a parent PA.
   106   
   107   template <class IndexT>
   108   class component_index
   109   {
   110   public://protected: (avoid friends for now)
   111     typedef std::vector<IndexT> MyIndexContainer;
   112     MyIndexContainer header;
   113     MyIndexContainer index;
   114     typedef typename MyIndexContainer::size_type SizeT;
   115     typedef typename MyIndexContainer::const_iterator IndexIter;
   116   public:
   117     typedef detail::component_iterator<IndexIter, IndexT, SizeT> 
   118       component_iterator;
   119     class component {
   120       friend class component_index;
   121     protected:
   122       IndexT number;
   123       const component_index<IndexT>* comp_ind_ptr;
   124       component(IndexT i, const component_index<IndexT>* p) 
   125         : number(i), comp_ind_ptr(p) {}
   126     public:
   127       typedef component_iterator iterator;
   128       typedef component_iterator const_iterator;
   129       typedef IndexT value_type;
   130       iterator begin() const {
   131         return iterator( comp_ind_ptr->index.begin(),
   132                          (comp_ind_ptr->header)[number] );
   133       }
   134       iterator end() const {
   135         return iterator( comp_ind_ptr->index.begin(), 
   136                          comp_ind_ptr->index.size() );
   137       }
   138     };
   139     typedef SizeT size_type;
   140     typedef component value_type;
   141     
   142 #if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
   143     template <class Iterator>
   144     component_index(Iterator first, Iterator last) 
   145     : index(std::distance(first, last))
   146     { 
   147       std::copy(first, last, index.begin());
   148       detail::construct_component_index(index, header);
   149     }
   150 #else
   151     template <class Iterator>
   152     component_index(Iterator first, Iterator last) 
   153       : index(first, last)
   154     { 
   155       detail::construct_component_index(index, header);
   156     }
   157 #endif
   158 
   159     component operator[](IndexT i) const {
   160       return component(i, this);
   161     }
   162     SizeT size() const {
   163       return header.size();
   164     }
   165     
   166   };
   167 
   168 } // namespace boost
   169 
   170 #endif // BOOST_INCREMENTAL_COMPONENTS_HPP