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