// | |
//======================================================================= | |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
//======================================================================= | |
// | |
#ifndef BOOST_DISJOINT_SETS_HPP | |
#define BOOST_DISJOINT_SETS_HPP | |
#include <vector> | |
#include <boost/graph/properties.hpp> | |
#include <boost/pending/detail/disjoint_sets.hpp> | |
namespace boost { | |
struct find_with_path_halving { | |
template <class ParentPA, class Vertex> | |
Vertex operator()(ParentPA p, Vertex v) { | |
return detail::find_representative_with_path_halving(p, v); | |
} | |
}; | |
struct find_with_full_path_compression { | |
template <class ParentPA, class Vertex> | |
Vertex operator()(ParentPA p, Vertex v){ | |
return detail::find_representative_with_full_compression(p, v); | |
} | |
}; | |
// This is a generalized functor to provide disjoint sets operations | |
// with "union by rank" and "path compression". A disjoint-set data | |
// structure maintains a collection S={S1, S2, ..., Sk} of disjoint | |
// sets. Each set is identified by a representative, which is some | |
// member of of the set. Sets are represented by rooted trees. Two | |
// heuristics: "union by rank" and "path compression" are used to | |
// speed up the operations. | |
// Disjoint Set requires two vertex properties for internal use. A | |
// RankPA and a ParentPA. The RankPA must map Vertex to some Integral type | |
// (preferably the size_type associated with Vertex). The ParentPA | |
// must map Vertex to Vertex. | |
template <class RankPA, class ParentPA, | |
class FindCompress = find_with_full_path_compression | |
> | |
class disjoint_sets { | |
typedef disjoint_sets self; | |
inline disjoint_sets() {} | |
public: | |
inline disjoint_sets(RankPA r, ParentPA p) | |
: rank(r), parent(p) {} | |
inline disjoint_sets(const self& c) | |
: rank(c.rank), parent(c.parent) {} | |
// Make Set -- Create a singleton set containing vertex x | |
template <class Element> | |
inline void make_set(Element x) | |
{ | |
put(parent, x, x); | |
typedef typename property_traits<RankPA>::value_type R; | |
put(rank, x, R()); | |
} | |
// Link - union the two sets represented by vertex x and y | |
template <class Element> | |
inline void link(Element x, Element y) | |
{ | |
detail::link_sets(parent, rank, x, y, rep); | |
} | |
// Union-Set - union the two sets containing vertex x and y | |
template <class Element> | |
inline void union_set(Element x, Element y) | |
{ | |
link(find_set(x), find_set(y)); | |
} | |
// Find-Set - returns the Element representative of the set | |
// containing Element x and applies path compression. | |
template <class Element> | |
inline Element find_set(Element x) | |
{ | |
return rep(parent, x); | |
} | |
template <class ElementIterator> | |
inline std::size_t count_sets(ElementIterator first, ElementIterator last) | |
{ | |
std::size_t count = 0; | |
for ( ; first != last; ++first) | |
if (get(parent, *first) == *first) | |
++count; | |
return count; | |
} | |
template <class ElementIterator> | |
inline void normalize_sets(ElementIterator first, ElementIterator last) | |
{ | |
for (; first != last; ++first) | |
detail::normalize_node(parent, *first); | |
} | |
template <class ElementIterator> | |
inline void compress_sets(ElementIterator first, ElementIterator last) | |
{ | |
for (; first != last; ++first) | |
detail::find_representative_with_full_compression(parent, *first); | |
} | |
protected: | |
RankPA rank; | |
ParentPA parent; | |
FindCompress rep; | |
}; | |
template <class ID = identity_property_map, | |
class InverseID = identity_property_map, | |
class FindCompress = find_with_full_path_compression | |
> | |
class disjoint_sets_with_storage | |
{ | |
typedef typename property_traits<ID>::value_type Index; | |
typedef std::vector<Index> ParentContainer; | |
typedef std::vector<unsigned char> RankContainer; | |
public: | |
typedef typename ParentContainer::size_type size_type; | |
disjoint_sets_with_storage(size_type n = 0, | |
ID id_ = ID(), | |
InverseID inv = InverseID()) | |
: id(id_), id_to_vertex(inv), rank(n, 0), parent(n) | |
{ | |
for (Index i = 0; i < n; ++i) | |
parent[i] = i; | |
} | |
// note this is not normally needed | |
template <class Element> | |
inline void | |
make_set(Element x) { | |
parent[x] = x; | |
rank[x] = 0; | |
} | |
template <class Element> | |
inline void | |
link(Element x, Element y) | |
{ | |
extend_sets(x,y); | |
detail::link_sets(&parent[0], &rank[0], | |
get(id,x), get(id,y), rep); | |
} | |
template <class Element> | |
inline void | |
union_set(Element x, Element y) { | |
Element rx = find_set(x); | |
Element ry = find_set(y); | |
link(rx, ry); | |
} | |
template <class Element> | |
inline Element find_set(Element x) { | |
return id_to_vertex[rep(&parent[0], get(id,x))]; | |
} | |
template <class ElementIterator> | |
inline std::size_t count_sets(ElementIterator first, ElementIterator last) | |
{ | |
std::size_t count = 0; | |
for ( ; first != last; ++first) | |
if (parent[*first] == *first) | |
++count; | |
return count; | |
} | |
template <class ElementIterator> | |
inline void normalize_sets(ElementIterator first, ElementIterator last) | |
{ | |
for (; first != last; ++first) | |
detail::normalize_node(&parent[0], *first); | |
} | |
template <class ElementIterator> | |
inline void compress_sets(ElementIterator first, ElementIterator last) | |
{ | |
for (; first != last; ++first) | |
detail::find_representative_with_full_compression(&parent[0], | |
*first); | |
} | |
const ParentContainer& parents() { return parent; } | |
protected: | |
template <class Element> | |
inline void | |
extend_sets(Element x, Element y) | |
{ | |
Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1; | |
if (needed > parent.size()) { | |
rank.insert(rank.end(), needed - rank.size(), 0); | |
for (Index k = parent.size(); k < needed; ++k) | |
parent.push_back(k); | |
} | |
} | |
ID id; | |
InverseID id_to_vertex; | |
RankContainer rank; | |
ParentContainer parent; | |
FindCompress rep; | |
}; | |
} // namespace boost | |
#endif // BOOST_DISJOINT_SETS_HPP |