| // (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 = get(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)) |
| put(rank, j, get(rank, j) + 1); |
| } |
| } |
| |
| // 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 |