1 | // |
2 | //======================================================================= |
3 | // Copyright 1997-2001 University of Notre Dame. |
4 | // Copyright 2009 Trustees of Indiana University. |
5 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen |
6 | // |
7 | // Distributed under the Boost Software License, Version 1.0. (See |
8 | // accompanying file LICENSE_1_0.txt or copy at |
9 | // http://www.boost.org/LICENSE_1_0.txt) |
10 | //======================================================================= |
11 | // |
12 | |
13 | #ifndef BOOST_INCREMENTAL_COMPONENTS_HPP |
14 | #define BOOST_INCREMENTAL_COMPONENTS_HPP |
15 | |
16 | #include <boost/detail/iterator.hpp> |
17 | #include <boost/graph/detail/incremental_components.hpp> |
18 | #include <boost/iterator/counting_iterator.hpp> |
19 | #include <boost/make_shared.hpp> |
20 | #include <boost/pending/disjoint_sets.hpp> |
21 | #include <iterator> |
22 | |
23 | namespace boost { |
24 | |
25 | // A connected component algorithm for the case when dynamically |
26 | // adding (but not removing) edges is common. The |
27 | // incremental_components() function is a preparing operation. Call |
28 | // same_component to check whether two vertices are in the same |
29 | // component, or use disjoint_set::find_set to determine the |
30 | // representative for a vertex. |
31 | |
32 | // This version of connected components does not require a full |
33 | // Graph. Instead, it just needs an edge list, where the vertices of |
34 | // each edge need to be of integer type. The edges are assumed to |
35 | // be undirected. The other difference is that the result is stored in |
36 | // a container, instead of just a decorator. The container should be |
37 | // empty before the algorithm is called. It will grow during the |
38 | // course of the algorithm. The container must be a model of |
39 | // BackInsertionSequence and RandomAccessContainer |
40 | // (std::vector is a good choice). After running the algorithm the |
41 | // index container will map each vertex to the representative |
42 | // vertex of the component to which it belongs. |
43 | // |
44 | // Adapted from an implementation by Alex Stepanov. The disjoint |
45 | // sets data structure is from Tarjan's "Data Structures and Network |
46 | // Algorithms", and the application to connected components is |
47 | // similar to the algorithm described in Ch. 22 of "Intro to |
48 | // Algorithms" by Cormen, et. all. |
49 | // |
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 (boost::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 (boost::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 | // Class that builds a quick-access indexed linked list that allows |
105 | // for fast iterating through a parent component's children. |
106 | template <typename IndexType> |
107 | class component_index { |
108 | |
109 | private: |
110 | typedef std::vector<IndexType> IndexContainer; |
111 | |
112 | public: |
113 | typedef counting_iterator<IndexType> iterator; |
114 | typedef iterator const_iterator; |
115 | typedef IndexType value_type; |
116 | typedef IndexType size_type; |
117 | |
118 | typedef detail::component_index_iterator<typename IndexContainer::iterator> |
119 | component_iterator; |
120 | |
121 | public: |
122 | template <typename ParentIterator, |
123 | typename ElementIndexMap> |
124 | component_index(ParentIterator parent_start, |
125 | ParentIterator parent_end, |
126 | const ElementIndexMap& index_map) : |
127 | m_num_elements(std::distance(parent_start, parent_end)), |
128 | m_components(make_shared<IndexContainer>()), |
129 | m_index_list(make_shared<IndexContainer>(m_num_elements)) { |
130 | |
131 | build_index_lists(parent_start, index_map); |
132 | |
133 | } // component_index |
134 | |
135 | template <typename ParentIterator> |
136 | component_index(ParentIterator parent_start, |
137 | ParentIterator parent_end) : |
138 | m_num_elements(std::distance(parent_start, parent_end)), |
139 | m_components(make_shared<IndexContainer>()), |
140 | m_index_list(make_shared<IndexContainer>(m_num_elements)) { |
141 | |
142 | build_index_lists(parent_start, boost::identity_property_map()); |
143 | |
144 | } // component_index |
145 | |
146 | // Returns the number of components |
147 | inline std::size_t size() const { |
148 | return (m_components->size()); |
149 | } |
150 | |
151 | // Beginning iterator for component indices |
152 | iterator begin() const { |
153 | return (iterator(0)); |
154 | } |
155 | |
156 | // End iterator for component indices |
157 | iterator end() const { |
158 | return (iterator(this->size())); |
159 | } |
160 | |
161 | // Returns a pair of begin and end iterators for the child |
162 | // elements of component [component_index]. |
163 | std::pair<component_iterator, component_iterator> |
164 | operator[](IndexType component_index) const { |
165 | |
166 | IndexType first_index = (*m_components)[component_index]; |
167 | |
168 | return (std::make_pair |
169 | (component_iterator(m_index_list->begin(), first_index), |
170 | component_iterator(m_num_elements))); |
171 | } |
172 | |
173 | private: |
174 | template <typename ParentIterator, |
175 | typename ElementIndexMap> |
176 | void build_index_lists(ParentIterator parent_start, |
177 | const ElementIndexMap& index_map) { |
178 | |
179 | typedef typename std::iterator_traits<ParentIterator>::value_type Element; |
180 | typename IndexContainer::iterator index_list = |
181 | m_index_list->begin(); |
182 | |
183 | // First pass - find root elements, construct index list |
184 | for (IndexType element_index = 0; element_index < m_num_elements; |
185 | ++element_index) { |
186 | |
187 | Element parent_element = parent_start[element_index]; |
188 | IndexType parent_index = get(index_map, parent_element); |
189 | |
190 | if (element_index != parent_index) { |
191 | index_list[element_index] = parent_index; |
192 | } |
193 | else { |
194 | m_components->push_back(element_index); |
195 | |
196 | // m_num_elements is the linked list terminator |
197 | index_list[element_index] = m_num_elements; |
198 | } |
199 | } |
200 | |
201 | // Second pass - build linked list |
202 | for (IndexType element_index = 0; element_index < m_num_elements; |
203 | ++element_index) { |
204 | |
205 | Element parent_element = parent_start[element_index]; |
206 | IndexType parent_index = get(index_map, parent_element); |
207 | |
208 | if (element_index != parent_index) { |
209 | |
210 | // Follow list until a component parent is found |
211 | while (index_list[parent_index] != m_num_elements) { |
212 | parent_index = index_list[parent_index]; |
213 | } |
214 | |
215 | // Push element to the front of the linked list |
216 | index_list[element_index] = index_list[parent_index]; |
217 | index_list[parent_index] = element_index; |
218 | } |
219 | } |
220 | |
221 | } // build_index_lists |
222 | |
223 | protected: |
224 | IndexType m_num_elements; |
225 | shared_ptr<IndexContainer> m_components, m_index_list; |
226 | |
227 | }; // class component_index |
228 | |
229 | } // namespace boost |
230 | |
231 | #endif // BOOST_INCREMENTAL_COMPONENTS_HPP |
232 | |