File indexing completed on 2025-01-30 09:43:00
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013 #ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
0014 #define BOOST_INCREMENTAL_COMPONENTS_HPP
0015
0016 #include <boost/tuple/tuple.hpp>
0017 #include <boost/graph/detail/incremental_components.hpp>
0018 #include <boost/iterator/counting_iterator.hpp>
0019 #include <boost/smart_ptr/make_shared.hpp>
0020 #include <boost/pending/disjoint_sets.hpp>
0021 #include <iterator>
0022
0023 namespace boost
0024 {
0025
0026
0027
0028
0029
0030
0031
0032
0033
0034
0035
0036
0037
0038
0039
0040
0041
0042
0043
0044
0045
0046
0047
0048
0049
0050
0051
0052
0053
0054
0055 template < class EdgeListGraph, class DisjointSets >
0056 void incremental_components(EdgeListGraph& g, DisjointSets& ds)
0057 {
0058 typename graph_traits< EdgeListGraph >::edge_iterator e, end;
0059 for (boost::tie(e, end) = edges(g); e != end; ++e)
0060 ds.union_set(source(*e, g), target(*e, g));
0061 }
0062
0063 template < class ParentIterator >
0064 void compress_components(ParentIterator first, ParentIterator last)
0065 {
0066 for (ParentIterator current = first; current != last; ++current)
0067 detail::find_representative_with_full_compression(
0068 first, current - first);
0069 }
0070
0071 template < class ParentIterator >
0072 typename std::iterator_traits< ParentIterator >::difference_type
0073 component_count(ParentIterator first, ParentIterator last)
0074 {
0075 std::ptrdiff_t count = 0;
0076 for (ParentIterator current = first; current != last; ++current)
0077 if (*current == current - first)
0078 ++count;
0079 return count;
0080 }
0081
0082
0083
0084
0085 template < class ParentIterator >
0086 void normalize_components(ParentIterator first, ParentIterator last)
0087 {
0088 for (ParentIterator current = first; current != last; ++current)
0089 detail::normalize_node(first, current - first);
0090 }
0091
0092 template < class VertexListGraph, class DisjointSets >
0093 void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
0094 {
0095 typename graph_traits< VertexListGraph >::vertex_iterator v, vend;
0096 for (boost::tie(v, vend) = vertices(G); v != vend; ++v)
0097 ds.make_set(*v);
0098 }
0099
0100 template < class Vertex, class DisjointSet >
0101 inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
0102 {
0103 return ds.find_set(u) == ds.find_set(v);
0104 }
0105
0106
0107
0108 template < typename IndexType > class component_index
0109 {
0110
0111 private:
0112 typedef std::vector< IndexType > IndexContainer;
0113
0114 public:
0115 typedef counting_iterator< IndexType > iterator;
0116 typedef iterator const_iterator;
0117 typedef IndexType value_type;
0118 typedef IndexType size_type;
0119
0120 typedef detail::component_index_iterator<
0121 typename IndexContainer::iterator >
0122 component_iterator;
0123
0124 public:
0125 template < typename ParentIterator, typename ElementIndexMap >
0126 component_index(ParentIterator parent_start, ParentIterator parent_end,
0127 const ElementIndexMap& index_map)
0128 : m_num_elements(std::distance(parent_start, parent_end))
0129 , m_components(make_shared< IndexContainer >())
0130 , m_index_list(make_shared< IndexContainer >(m_num_elements))
0131 {
0132
0133 build_index_lists(parent_start, index_map);
0134
0135 }
0136
0137 template < typename ParentIterator >
0138 component_index(ParentIterator parent_start, ParentIterator parent_end)
0139 : m_num_elements(std::distance(parent_start, parent_end))
0140 , m_components(make_shared< IndexContainer >())
0141 , m_index_list(make_shared< IndexContainer >(m_num_elements))
0142 {
0143
0144 build_index_lists(parent_start, boost::identity_property_map());
0145
0146 }
0147
0148
0149 inline std::size_t size() const { return (m_components->size()); }
0150
0151
0152 iterator begin() const { return (iterator(0)); }
0153
0154
0155 iterator end() const { return (iterator(this->size())); }
0156
0157
0158
0159 std::pair< component_iterator, component_iterator > operator[](
0160 IndexType component_index) const
0161 {
0162
0163 IndexType first_index = (*m_components)[component_index];
0164
0165 return (std::make_pair(
0166 component_iterator(m_index_list->begin(), first_index),
0167 component_iterator(m_num_elements)));
0168 }
0169
0170 private:
0171 template < typename ParentIterator, typename ElementIndexMap >
0172 void build_index_lists(
0173 ParentIterator parent_start, const ElementIndexMap& index_map)
0174 {
0175
0176 typedef
0177 typename std::iterator_traits< ParentIterator >::value_type Element;
0178 typename IndexContainer::iterator index_list = m_index_list->begin();
0179
0180
0181 for (IndexType element_index = 0; element_index < m_num_elements;
0182 ++element_index)
0183 {
0184
0185 Element parent_element = parent_start[element_index];
0186 IndexType parent_index = get(index_map, parent_element);
0187
0188 if (element_index != parent_index)
0189 {
0190 index_list[element_index] = parent_index;
0191 }
0192 else
0193 {
0194 m_components->push_back(element_index);
0195
0196
0197 index_list[element_index] = m_num_elements;
0198 }
0199 }
0200
0201
0202 for (IndexType element_index = 0; element_index < m_num_elements;
0203 ++element_index)
0204 {
0205
0206 Element parent_element = parent_start[element_index];
0207 IndexType parent_index = get(index_map, parent_element);
0208
0209 if (element_index != parent_index)
0210 {
0211
0212
0213 while (index_list[parent_index] != m_num_elements)
0214 {
0215 parent_index = index_list[parent_index];
0216 }
0217
0218
0219 index_list[element_index] = index_list[parent_index];
0220 index_list[parent_index] = element_index;
0221 }
0222 }
0223
0224 }
0225
0226 protected:
0227 IndexType m_num_elements;
0228 shared_ptr< IndexContainer > m_components, m_index_list;
0229
0230 };
0231
0232 }
0233
0234 #endif