disjoint_sets.hpp

CGAL is a collaborative effort of several sites in Europe and Israel. The goal is to make the most i

//
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// This file is part of the Generic Graph Component Library
//
// You should have received a copy of the License Agreement for the
// Generic Graph Component Library along with the software;  see the
// file LICENSE.  If not, contact Office of Research, University of Notre
// Dame, Notre Dame, IN  46556.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//=======================================================================
//
#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