source: NonGTP/Boost/boost/graph/incremental_components.hpp @ 857

Revision 857, 6.2 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]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
18namespace 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
Note: See TracBrowser for help on using the repository browser.