williamr@2
|
1 |
//
|
williamr@2
|
2 |
//=======================================================================
|
williamr@2
|
3 |
// Copyright 1997-2001 University of Notre Dame.
|
williamr@2
|
4 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
williamr@2
|
5 |
//
|
williamr@2
|
6 |
// Distributed under the Boost Software License, Version 1.0. (See
|
williamr@2
|
7 |
// accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
8 |
// http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
9 |
//=======================================================================
|
williamr@2
|
10 |
//
|
williamr@2
|
11 |
|
williamr@2
|
12 |
#ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
|
williamr@2
|
13 |
#define BOOST_INCREMENTAL_COMPONENTS_HPP
|
williamr@2
|
14 |
|
williamr@2
|
15 |
#include <boost/detail/iterator.hpp>
|
williamr@2
|
16 |
#include <boost/graph/detail/incremental_components.hpp>
|
williamr@2
|
17 |
|
williamr@2
|
18 |
namespace boost {
|
williamr@2
|
19 |
|
williamr@2
|
20 |
// A connected component algorithm for the case when dynamically
|
williamr@2
|
21 |
// adding (but not removing) edges is common. The
|
williamr@2
|
22 |
// incremental_components() function is a preparing operation. Call
|
williamr@2
|
23 |
// same_component to check whether two vertices are in the same
|
williamr@2
|
24 |
// component, or use disjoint_set::find_set to determine the
|
williamr@2
|
25 |
// representative for a vertex.
|
williamr@2
|
26 |
|
williamr@2
|
27 |
// This version of connected components does not require a full
|
williamr@2
|
28 |
// Graph. Instead, it just needs an edge list, where the vertices of
|
williamr@2
|
29 |
// each edge need to be of integer type. The edges are assumed to
|
williamr@2
|
30 |
// be undirected. The other difference is that the result is stored in
|
williamr@2
|
31 |
// a container, instead of just a decorator. The container should be
|
williamr@2
|
32 |
// empty before the algorithm is called. It will grow during the
|
williamr@2
|
33 |
// course of the algorithm. The container must be a model of
|
williamr@2
|
34 |
// BackInsertionSequence and RandomAccessContainer
|
williamr@2
|
35 |
// (std::vector is a good choice). After running the algorithm the
|
williamr@2
|
36 |
// index container will map each vertex to the representative
|
williamr@2
|
37 |
// vertex of the component to which it belongs.
|
williamr@2
|
38 |
//
|
williamr@2
|
39 |
// Adapted from an implementation by Alex Stepanov. The disjoint
|
williamr@2
|
40 |
// sets data structure is from Tarjan's "Data Structures and Network
|
williamr@2
|
41 |
// Algorithms", and the application to connected components is
|
williamr@2
|
42 |
// similar to the algorithm described in Ch. 22 of "Intro to
|
williamr@2
|
43 |
// Algorithms" by Cormen, et. all.
|
williamr@2
|
44 |
//
|
williamr@2
|
45 |
// RankContainer is a random accessable container (operator[] is
|
williamr@2
|
46 |
// defined) with a value type that can represent an integer part of
|
williamr@2
|
47 |
// a binary log of the value type of the corresponding
|
williamr@2
|
48 |
// ParentContainer (char is always enough) its size_type is no less
|
williamr@2
|
49 |
// than the size_type of the corresponding ParentContainer
|
williamr@2
|
50 |
|
williamr@2
|
51 |
// An implementation of disjoint sets can be found in
|
williamr@2
|
52 |
// boost/pending/disjoint_sets.hpp
|
williamr@2
|
53 |
|
williamr@2
|
54 |
template <class EdgeListGraph, class DisjointSets>
|
williamr@2
|
55 |
void incremental_components(EdgeListGraph& g, DisjointSets& ds)
|
williamr@2
|
56 |
{
|
williamr@2
|
57 |
typename graph_traits<EdgeListGraph>::edge_iterator e, end;
|
williamr@2
|
58 |
for (tie(e,end) = edges(g); e != end; ++e)
|
williamr@2
|
59 |
ds.union_set(source(*e,g),target(*e,g));
|
williamr@2
|
60 |
}
|
williamr@2
|
61 |
|
williamr@2
|
62 |
template <class ParentIterator>
|
williamr@2
|
63 |
void compress_components(ParentIterator first, ParentIterator last)
|
williamr@2
|
64 |
{
|
williamr@2
|
65 |
for (ParentIterator current = first; current != last; ++current)
|
williamr@2
|
66 |
detail::find_representative_with_full_compression(first, current-first);
|
williamr@2
|
67 |
}
|
williamr@2
|
68 |
|
williamr@2
|
69 |
template <class ParentIterator>
|
williamr@2
|
70 |
typename boost::detail::iterator_traits<ParentIterator>::difference_type
|
williamr@2
|
71 |
component_count(ParentIterator first, ParentIterator last)
|
williamr@2
|
72 |
{
|
williamr@2
|
73 |
std::ptrdiff_t count = 0;
|
williamr@2
|
74 |
for (ParentIterator current = first; current != last; ++current)
|
williamr@2
|
75 |
if (*current == current - first) ++count;
|
williamr@2
|
76 |
return count;
|
williamr@2
|
77 |
}
|
williamr@2
|
78 |
|
williamr@2
|
79 |
// This algorithm can be applied to the result container of the
|
williamr@2
|
80 |
// connected_components algorithm to normalize
|
williamr@2
|
81 |
// the components.
|
williamr@2
|
82 |
template <class ParentIterator>
|
williamr@2
|
83 |
void normalize_components(ParentIterator first, ParentIterator last)
|
williamr@2
|
84 |
{
|
williamr@2
|
85 |
for (ParentIterator current = first; current != last; ++current)
|
williamr@2
|
86 |
detail::normalize_node(first, current - first);
|
williamr@2
|
87 |
}
|
williamr@2
|
88 |
|
williamr@2
|
89 |
template <class VertexListGraph, class DisjointSets>
|
williamr@2
|
90 |
void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
|
williamr@2
|
91 |
{
|
williamr@2
|
92 |
typename graph_traits<VertexListGraph>
|
williamr@2
|
93 |
::vertex_iterator v, vend;
|
williamr@2
|
94 |
for (tie(v, vend) = vertices(G); v != vend; ++v)
|
williamr@2
|
95 |
ds.make_set(*v);
|
williamr@2
|
96 |
}
|
williamr@2
|
97 |
|
williamr@2
|
98 |
template <class Vertex, class DisjointSet>
|
williamr@2
|
99 |
inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
|
williamr@2
|
100 |
{
|
williamr@2
|
101 |
return ds.find_set(u) == ds.find_set(v);
|
williamr@2
|
102 |
}
|
williamr@2
|
103 |
|
williamr@2
|
104 |
// considering changing the so that it initializes with a pair of
|
williamr@2
|
105 |
// vertex iterators and a parent PA.
|
williamr@2
|
106 |
|
williamr@2
|
107 |
template <class IndexT>
|
williamr@2
|
108 |
class component_index
|
williamr@2
|
109 |
{
|
williamr@2
|
110 |
public://protected: (avoid friends for now)
|
williamr@2
|
111 |
typedef std::vector<IndexT> MyIndexContainer;
|
williamr@2
|
112 |
MyIndexContainer header;
|
williamr@2
|
113 |
MyIndexContainer index;
|
williamr@2
|
114 |
typedef typename MyIndexContainer::size_type SizeT;
|
williamr@2
|
115 |
typedef typename MyIndexContainer::const_iterator IndexIter;
|
williamr@2
|
116 |
public:
|
williamr@2
|
117 |
typedef detail::component_iterator<IndexIter, IndexT, SizeT>
|
williamr@2
|
118 |
component_iterator;
|
williamr@2
|
119 |
class component {
|
williamr@2
|
120 |
friend class component_index;
|
williamr@2
|
121 |
protected:
|
williamr@2
|
122 |
IndexT number;
|
williamr@2
|
123 |
const component_index<IndexT>* comp_ind_ptr;
|
williamr@2
|
124 |
component(IndexT i, const component_index<IndexT>* p)
|
williamr@2
|
125 |
: number(i), comp_ind_ptr(p) {}
|
williamr@2
|
126 |
public:
|
williamr@2
|
127 |
typedef component_iterator iterator;
|
williamr@2
|
128 |
typedef component_iterator const_iterator;
|
williamr@2
|
129 |
typedef IndexT value_type;
|
williamr@2
|
130 |
iterator begin() const {
|
williamr@2
|
131 |
return iterator( comp_ind_ptr->index.begin(),
|
williamr@2
|
132 |
(comp_ind_ptr->header)[number] );
|
williamr@2
|
133 |
}
|
williamr@2
|
134 |
iterator end() const {
|
williamr@2
|
135 |
return iterator( comp_ind_ptr->index.begin(),
|
williamr@2
|
136 |
comp_ind_ptr->index.size() );
|
williamr@2
|
137 |
}
|
williamr@2
|
138 |
};
|
williamr@2
|
139 |
typedef SizeT size_type;
|
williamr@2
|
140 |
typedef component value_type;
|
williamr@2
|
141 |
|
williamr@2
|
142 |
#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
|
williamr@2
|
143 |
template <class Iterator>
|
williamr@2
|
144 |
component_index(Iterator first, Iterator last)
|
williamr@2
|
145 |
: index(std::distance(first, last))
|
williamr@2
|
146 |
{
|
williamr@2
|
147 |
std::copy(first, last, index.begin());
|
williamr@2
|
148 |
detail::construct_component_index(index, header);
|
williamr@2
|
149 |
}
|
williamr@2
|
150 |
#else
|
williamr@2
|
151 |
template <class Iterator>
|
williamr@2
|
152 |
component_index(Iterator first, Iterator last)
|
williamr@2
|
153 |
: index(first, last)
|
williamr@2
|
154 |
{
|
williamr@2
|
155 |
detail::construct_component_index(index, header);
|
williamr@2
|
156 |
}
|
williamr@2
|
157 |
#endif
|
williamr@2
|
158 |
|
williamr@2
|
159 |
component operator[](IndexT i) const {
|
williamr@2
|
160 |
return component(i, this);
|
williamr@2
|
161 |
}
|
williamr@2
|
162 |
SizeT size() const {
|
williamr@2
|
163 |
return header.size();
|
williamr@2
|
164 |
}
|
williamr@2
|
165 |
|
williamr@2
|
166 |
};
|
williamr@2
|
167 |
|
williamr@2
|
168 |
} // namespace boost
|
williamr@2
|
169 |
|
williamr@2
|
170 |
#endif // BOOST_INCREMENTAL_COMPONENTS_HPP
|