1 // (C) Copyright Jeremy Siek 2004 2 // Distributed under the Boost Software License, Version 1.0. (See 3 // accompanying file LICENSE_1_0.txt or copy at 4 // http://www.boost.org/LICENSE_1_0.txt) 5 6 #ifndef BOOST_DETAIL_DISJOINT_SETS_HPP 7 #define BOOST_DETAIL_DISJOINT_SETS_HPP 8 9 namespace boost 10 { 11 12 namespace detail 13 { 14 15 template < class ParentPA, class Vertex > find_representative_with_path_halving(ParentPA p,Vertex v)16 Vertex find_representative_with_path_halving(ParentPA p, Vertex v) 17 { 18 Vertex parent = get(p, v); 19 Vertex grandparent = get(p, parent); 20 while (parent != grandparent) 21 { 22 put(p, v, grandparent); 23 v = grandparent; 24 parent = get(p, v); 25 grandparent = get(p, parent); 26 } 27 return parent; 28 } 29 30 template < class ParentPA, class Vertex > find_representative_with_full_compression(ParentPA parent,Vertex v)31 Vertex find_representative_with_full_compression(ParentPA parent, Vertex v) 32 { 33 Vertex old = v; 34 Vertex ancestor = get(parent, v); 35 while (ancestor != v) 36 { 37 v = ancestor; 38 ancestor = get(parent, v); 39 } 40 v = get(parent, old); 41 while (ancestor != v) 42 { 43 put(parent, old, ancestor); 44 old = v; 45 v = get(parent, old); 46 } 47 return ancestor; 48 } 49 50 /* the postcondition of link sets is: 51 component_representative(i) == component_representative(j) 52 */ 53 template < class ParentPA, class RankPA, class Vertex, 54 class ComponentRepresentative > link_sets(ParentPA p,RankPA rank,Vertex i,Vertex j,ComponentRepresentative comp_rep)55 inline void link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j, 56 ComponentRepresentative comp_rep) 57 { 58 i = comp_rep(p, i); 59 j = comp_rep(p, j); 60 if (i == j) 61 return; 62 if (get(rank, i) > get(rank, j)) 63 put(p, j, i); 64 else 65 { 66 put(p, i, j); 67 if (get(rank, i) == get(rank, j)) 68 put(rank, j, get(rank, j) + 1); 69 } 70 } 71 72 // normalize components has the following postcondidition: 73 // i >= p[i] 74 // that is, the representative is the node with the smallest index in its 75 // class as its precondition it it assumes that the node container is 76 // compressed 77 78 template < class ParentPA, class Vertex > normalize_node(ParentPA p,Vertex i)79 inline void normalize_node(ParentPA p, Vertex i) 80 { 81 if (i > get(p, i) || get(p, get(p, i)) != get(p, i)) 82 put(p, i, get(p, get(p, i))); 83 else 84 { 85 put(p, get(p, i), i); 86 put(p, i, i); 87 } 88 } 89 90 } // namespace detail 91 } // namespace boost 92 93 #endif // BOOST_DETAIL_DISJOINT_SETS_HPP 94