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