pending/detail/disjoint_sets.hpp

0001 //  (C) Copyright Jeremy Siek 2004
0002 //  Distributed under the Boost Software License, Version 1.0. (See
0003 //  accompanying file LICENSE_1_0.txt or copy at
0004 //  http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_DETAIL_DISJOINT_SETS_HPP
0007 #define BOOST_DETAIL_DISJOINT_SETS_HPP
0008
0009 namespace boost
0010 {
0011
0012 namespace detail
0013 {
0014
0015     template < class ParentPA, class Vertex >
0016     Vertex find_representative_with_path_halving(ParentPA p, Vertex v)
0017     {
0018         Vertex parent = get(p, v);
0019         Vertex grandparent = get(p, parent);
0020         while (parent != grandparent)
0021         {
0022             put(p, v, grandparent);
0023             v = grandparent;
0024             parent = get(p, v);
0025             grandparent = get(p, parent);
0026         }
0027         return parent;
0028     }
0029
0030     template < class ParentPA, class Vertex >
0031     Vertex find_representative_with_full_compression(ParentPA parent, Vertex v)
0032     {
0033         Vertex old = v;
0034         Vertex ancestor = get(parent, v);
0035         while (ancestor != v)
0036         {
0037             v = ancestor;
0038             ancestor = get(parent, v);
0039         }
0040         v = get(parent, old);
0041         while (ancestor != v)
0042         {
0043             put(parent, old, ancestor);
0044             old = v;
0045             v = get(parent, old);
0046         }
0047         return ancestor;
0048     }
0049
0050     /* the postcondition of link sets is:
0051      component_representative(i) == component_representative(j)
0052      */
0053     template < class ParentPA, class RankPA, class Vertex,
0054         class ComponentRepresentative >
0055     inline void link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j,
0056         ComponentRepresentative comp_rep)
0057     {
0058         i = comp_rep(p, i);
0059         j = comp_rep(p, j);
0060         if (i == j)
0061             return;
0062         if (get(rank, i) > get(rank, j))
0063             put(p, j, i);
0064         else
0065         {
0066             put(p, i, j);
0067             if (get(rank, i) == get(rank, j))
0068                 put(rank, j, get(rank, j) + 1);
0069         }
0070     }
0071
0072     // normalize components has the following postcondidition:
0073     // i >= p[i]
0074     // that is, the representative is the node with the smallest index in its
0075     // class as its precondition it it assumes that the node container is
0076     // compressed
0077
0078     template < class ParentPA, class Vertex >
0079     inline void normalize_node(ParentPA p, Vertex i)
0080     {
0081         if (i > get(p, i) || get(p, get(p, i)) != get(p, i))
0082             put(p, i, get(p, get(p, i)));
0083         else
0084         {
0085             put(p, get(p, i), i);
0086             put(p, i, i);
0087         }
0088     }
0089
0090 } // namespace detail
0091 } // namespace boost
0092
0093 #endif // BOOST_DETAIL_DISJOINT_SETS_HPP