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 #include <cassert>
0010
0011 namespace boost
0012 {
0013
0014 namespace detail
0015 {
0016
0017     template < class ParentPA, class Vertex >
0018     Vertex find_representative_with_path_halving(ParentPA p, Vertex v)
0019     {
0020         Vertex parent = get(p, v);
0021         Vertex grandparent = get(p, parent);
0022         while (parent != grandparent)
0023         {
0024             put(p, v, grandparent);
0025             v = grandparent;
0026             parent = get(p, v);
0027             grandparent = get(p, parent);
0028         }
0029         return parent;
0030     }
0031
0032     template < class ParentPA, class Vertex >
0033     Vertex find_representative_with_full_compression(ParentPA parent, Vertex v)
0034     {
0035         Vertex old = v;
0036         Vertex ancestor = get(parent, v);
0037         while (ancestor != v)
0038         {
0039             v = ancestor;
0040             ancestor = get(parent, v);
0041         }
0042         v = get(parent, old);
0043         while (ancestor != v)
0044         {
0045             put(parent, old, ancestor);
0046             old = v;
0047             v = get(parent, old);
0048         }
0049         return ancestor;
0050     }
0051
0052     /* the postcondition of link sets is:
0053      component_representative(i) == component_representative(j)
0054      */
0055     template < class ParentPA, class RankPA, class Vertex>
0056     inline void link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j)
0057     {
0058         assert(i == get(p, i));
0059         assert(j == get(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