disjoint_sets.hpp

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

//  (C) Copyright Jeremy Siek 2004 
//  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_DETAIL_DISJOINT_SETS_HPP
#define BOOST_DETAIL_DISJOINT_SETS_HPP

namespace boost {

namespace detail {

template <class ParentPA, class Vertex>
Vertex
find_representative_with_path_halving(ParentPA p, Vertex v)
{ 
  Vertex parent = get(p, v);
  Vertex grandparent = get(p, parent);
  while (parent != grandparent) {
    put(p, v, grandparent);
    v =  grandparent;
    parent = get(p, v);
    grandparent = get(p, parent); 
  }
  return parent;
}

template <class ParentPA, class Vertex>
Vertex
find_representative_with_full_compression(ParentPA parent, Vertex v)
{
  Vertex old = v;
  Vertex ancestor = get(parent, v);
  while (ancestor != v) {
    v = ancestor;
    ancestor = get(parent, v);
  }
  v = parent[old];
  while (ancestor != v) {
    put(parent, old, ancestor);
    old = v;
    v = get(parent, old);
  }
  return ancestor;
}

/* the postcondition of link sets is:
 component_representative(i) == component_representative(j)
 */
template <class ParentPA, class RankPA, class Vertex, 
          class ComponentRepresentative>
inline void
link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j,
          ComponentRepresentative comp_rep)
{
  i = comp_rep(p, i);
  j = comp_rep(p, j);
  if (i == j) return;
  if (get(rank, i) > get(rank, j)) 
    put(p, j, i);
  else {
    put(p, i, j);
    if (get(rank, i) == get(rank, j)) 
      ++rank[j];
  }
}  

// normalize components has the following postcondidition:
// i >= p[i]
// that is, the representative is the node with the smallest index in its class
// as its precondition it it assumes that the node container is compressed

template <class ParentPA, class Vertex>
inline void
normalize_node(ParentPA p, Vertex i)
{
  if (i > get(p,i) || get(p, get(p,i)) != get(p,i))   
    put(p,i, get(p, get(p,i)));
  else {
    put(p, get(p,i), i);
    put(p, i, i);
  } 
}

  } // namespace detail
} // namespace boost

#endif // BOOST_DETAIL_DISJOINT_SETS_HPP