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