]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |