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