Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / incremental_components.hpp
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