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
23namespace 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

source code of boost/boost/graph/incremental_components.hpp