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
26 // A connected component algorithm for the case when dynamically
27 // adding (but not removing) edges is common. The
28 // incremental_components() function is a preparing operation. Call
29 // same_component to check whether two vertices are in the same
30 // component, or use disjoint_set::find_set to determine the
31 // representative for a vertex.
32
33 // This version of connected components does not require a full
34 // Graph. Instead, it just needs an edge list, where the vertices of
35 // each edge need to be of integer type. The edges are assumed to
36 // be undirected. The other difference is that the result is stored in
37 // a container, instead of just a decorator. The container should be
38 // empty before the algorithm is called. It will grow during the
39 // course of the algorithm. The container must be a model of
40 // BackInsertionSequence and RandomAccessContainer
41 // (std::vector is a good choice). After running the algorithm the
42 // index container will map each vertex to the representative
43 // vertex of the component to which it belongs.
44 //
45 // Adapted from an implementation by Alex Stepanov. The disjoint
46 // sets data structure is from Tarjan's "Data Structures and Network
47 // Algorithms", and the application to connected components is
48 // similar to the algorithm described in Ch. 22 of "Intro to
49 // Algorithms" by Cormen, et. all.
50 //
51
52 // An implementation of disjoint sets can be found in
53 // boost/pending/disjoint_sets.hpp
54
55 template < class EdgeListGraph, class DisjointSets >
incremental_components(EdgeListGraph & g,DisjointSets & ds)56 void incremental_components(EdgeListGraph& g, DisjointSets& ds)
57 {
58 typename graph_traits< EdgeListGraph >::edge_iterator e, end;
59 for (boost::tie(e, end) = edges(g); e != end; ++e)
60 ds.union_set(source(*e, g), target(*e, g));
61 }
62
63 template < class ParentIterator >
compress_components(ParentIterator first,ParentIterator last)64 void compress_components(ParentIterator first, ParentIterator last)
65 {
66 for (ParentIterator current = first; current != last; ++current)
67 detail::find_representative_with_full_compression(
68 first, current - first);
69 }
70
71 template < class ParentIterator >
72 typename boost::detail::iterator_traits< ParentIterator >::difference_type
component_count(ParentIterator first,ParentIterator last)73 component_count(ParentIterator first, ParentIterator last)
74 {
75 std::ptrdiff_t count = 0;
76 for (ParentIterator current = first; current != last; ++current)
77 if (*current == current - first)
78 ++count;
79 return count;
80 }
81
82 // This algorithm can be applied to the result container of the
83 // connected_components algorithm to normalize
84 // the components.
85 template < class ParentIterator >
normalize_components(ParentIterator first,ParentIterator last)86 void normalize_components(ParentIterator first, ParentIterator last)
87 {
88 for (ParentIterator current = first; current != last; ++current)
89 detail::normalize_node(first, current - first);
90 }
91
92 template < class VertexListGraph, class DisjointSets >
initialize_incremental_components(VertexListGraph & G,DisjointSets & ds)93 void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
94 {
95 typename graph_traits< VertexListGraph >::vertex_iterator v, vend;
96 for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
97 ds.make_set(*v);
98 }
99
100 template < class Vertex, class DisjointSet >
same_component(Vertex u,Vertex v,DisjointSet & ds)101 inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
102 {
103 return ds.find_set(u) == ds.find_set(v);
104 }
105
106 // Class that builds a quick-access indexed linked list that allows
107 // for fast iterating through a parent component's children.
108 template < typename IndexType > class component_index
109 {
110
111 private:
112 typedef std::vector< IndexType > IndexContainer;
113
114 public:
115 typedef counting_iterator< IndexType > iterator;
116 typedef iterator const_iterator;
117 typedef IndexType value_type;
118 typedef IndexType size_type;
119
120 typedef detail::component_index_iterator<
121 typename IndexContainer::iterator >
122 component_iterator;
123
124 public:
125 template < typename ParentIterator, typename ElementIndexMap >
component_index(ParentIterator parent_start,ParentIterator parent_end,const ElementIndexMap & index_map)126 component_index(ParentIterator parent_start, ParentIterator parent_end,
127 const ElementIndexMap& index_map)
128 : m_num_elements(std::distance(parent_start, parent_end))
129 , m_components(make_shared< IndexContainer >())
130 , m_index_list(make_shared< IndexContainer >(m_num_elements))
131 {
132
133 build_index_lists(parent_start, index_map);
134
135 } // component_index
136
137 template < typename ParentIterator >
component_index(ParentIterator parent_start,ParentIterator parent_end)138 component_index(ParentIterator parent_start, ParentIterator parent_end)
139 : m_num_elements(std::distance(parent_start, parent_end))
140 , m_components(make_shared< IndexContainer >())
141 , m_index_list(make_shared< IndexContainer >(m_num_elements))
142 {
143
144 build_index_lists(parent_start, boost::identity_property_map());
145
146 } // component_index
147
148 // Returns the number of components
size() const149 inline std::size_t size() const { return (m_components->size()); }
150
151 // Beginning iterator for component indices
begin() const152 iterator begin() const { return (iterator(0)); }
153
154 // End iterator for component indices
end() const155 iterator end() const { return (iterator(this->size())); }
156
157 // Returns a pair of begin and end iterators for the child
158 // elements of component [component_index].
operator [](IndexType component_index) const159 std::pair< component_iterator, component_iterator > operator[](
160 IndexType component_index) const
161 {
162
163 IndexType first_index = (*m_components)[component_index];
164
165 return (std::make_pair(
166 component_iterator(m_index_list->begin(), first_index),
167 component_iterator(m_num_elements)));
168 }
169
170 private:
171 template < typename ParentIterator, typename ElementIndexMap >
build_index_lists(ParentIterator parent_start,const ElementIndexMap & index_map)172 void build_index_lists(
173 ParentIterator parent_start, const ElementIndexMap& index_map)
174 {
175
176 typedef
177 typename std::iterator_traits< ParentIterator >::value_type Element;
178 typename IndexContainer::iterator index_list = m_index_list->begin();
179
180 // First pass - find root elements, construct index list
181 for (IndexType element_index = 0; element_index < m_num_elements;
182 ++element_index)
183 {
184
185 Element parent_element = parent_start[element_index];
186 IndexType parent_index = get(index_map, parent_element);
187
188 if (element_index != parent_index)
189 {
190 index_list[element_index] = parent_index;
191 }
192 else
193 {
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
206 Element parent_element = parent_start[element_index];
207 IndexType parent_index = get(index_map, parent_element);
208
209 if (element_index != parent_index)
210 {
211
212 // Follow list until a component parent is found
213 while (index_list[parent_index] != m_num_elements)
214 {
215 parent_index = index_list[parent_index];
216 }
217
218 // Push element to the front of the linked list
219 index_list[element_index] = index_list[parent_index];
220 index_list[parent_index] = element_index;
221 }
222 }
223
224 } // build_index_lists
225
226 protected:
227 IndexType m_num_elements;
228 shared_ptr< IndexContainer > m_components, m_index_list;
229
230 }; // class component_index
231
232 } // namespace boost
233
234 #endif // BOOST_INCREMENTAL_COMPONENTS_HPP
235