Chris@16: //  (C) Copyright Jeremy Siek 2004 
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: #ifndef BOOST_DETAIL_DISJOINT_SETS_HPP
Chris@16: #define BOOST_DETAIL_DISJOINT_SETS_HPP
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <class ParentPA, class Vertex>
Chris@16: Vertex
Chris@16: find_representative_with_path_halving(ParentPA p, Vertex v)
Chris@16: { 
Chris@16:   Vertex parent = get(p, v);
Chris@16:   Vertex grandparent = get(p, parent);
Chris@16:   while (parent != grandparent) {
Chris@16:     put(p, v, grandparent);
Chris@16:     v =  grandparent;
Chris@16:     parent = get(p, v);
Chris@16:     grandparent = get(p, parent); 
Chris@16:   }
Chris@16:   return parent;
Chris@16: }
Chris@16: 
Chris@16: template <class ParentPA, class Vertex>
Chris@16: Vertex
Chris@16: find_representative_with_full_compression(ParentPA parent, Vertex v)
Chris@16: {
Chris@16:   Vertex old = v;
Chris@16:   Vertex ancestor = get(parent, v);
Chris@16:   while (ancestor != v) {
Chris@16:     v = ancestor;
Chris@16:     ancestor = get(parent, v);
Chris@16:   }
Chris@16:   v = get(parent, old);
Chris@16:   while (ancestor != v) {
Chris@16:     put(parent, old, ancestor);
Chris@16:     old = v;
Chris@16:     v = get(parent, old);
Chris@16:   }
Chris@16:   return ancestor;
Chris@16: }
Chris@16: 
Chris@16: /* the postcondition of link sets is:
Chris@16:  component_representative(i) == component_representative(j)
Chris@16:  */
Chris@16: template <class ParentPA, class RankPA, class Vertex, 
Chris@16:           class ComponentRepresentative>
Chris@16: inline void
Chris@16: link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j,
Chris@16:           ComponentRepresentative comp_rep)
Chris@16: {
Chris@16:   i = comp_rep(p, i);
Chris@16:   j = comp_rep(p, j);
Chris@16:   if (i == j) return;
Chris@16:   if (get(rank, i) > get(rank, j)) 
Chris@16:     put(p, j, i);
Chris@16:   else {
Chris@16:     put(p, i, j);
Chris@16:     if (get(rank, i) == get(rank, j)) 
Chris@16:       put(rank, j, get(rank, j) + 1);
Chris@16:   }
Chris@16: }  
Chris@16: 
Chris@16: // normalize components has the following postcondidition:
Chris@16: // i >= p[i]
Chris@16: // that is, the representative is the node with the smallest index in its class
Chris@16: // as its precondition it it assumes that the node container is compressed
Chris@16: 
Chris@16: template <class ParentPA, class Vertex>
Chris@16: inline void
Chris@16: normalize_node(ParentPA p, Vertex i)
Chris@16: {
Chris@16:   if (i > get(p,i) || get(p, get(p,i)) != get(p,i))   
Chris@16:     put(p,i, get(p, get(p,i)));
Chris@16:   else {
Chris@16:     put(p, get(p,i), i);
Chris@16:     put(p, i, i);
Chris@16:   } 
Chris@16: }
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_DETAIL_DISJOINT_SETS_HPP