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