| // |
| //======================================================================= |
| // 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 |