source: NonGTP/Boost/boost/pending/detail/disjoint_sets.hpp @ 857

Revision 857, 2.2 KB checked in by igarcia, 19 years ago (diff)
Line 
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
9namespace boost {
10
11namespace detail {
12
13template <class ParentPA, class Vertex>
14Vertex
15find_representative_with_path_halving(ParentPA p, Vertex v)
16{
17  Vertex parent = get(p, v);
18  Vertex grandparent = get(p, parent);
19  while (parent != grandparent) {
20    put(p, v, grandparent);
21    v =  grandparent;
22    parent = get(p, v);
23    grandparent = get(p, parent);
24  }
25  return parent;
26}
27
28template <class ParentPA, class Vertex>
29Vertex
30find_representative_with_full_compression(ParentPA parent, Vertex v)
31{
32  Vertex old = v;
33  Vertex ancestor = get(parent, v);
34  while (ancestor != v) {
35    v = ancestor;
36    ancestor = get(parent, v);
37  }
38  v = get(parent, old);
39  while (ancestor != v) {
40    put(parent, old, ancestor);
41    old = v;
42    v = get(parent, old);
43  }
44  return ancestor;
45}
46
47/* the postcondition of link sets is:
48 component_representative(i) == component_representative(j)
49 */
50template <class ParentPA, class RankPA, class Vertex,
51          class ComponentRepresentative>
52inline void
53link_sets(ParentPA p, RankPA rank, Vertex i, Vertex j,
54          ComponentRepresentative comp_rep)
55{
56  i = comp_rep(p, i);
57  j = comp_rep(p, j);
58  if (i == j) return;
59  if (get(rank, i) > get(rank, j))
60    put(p, j, i);
61  else {
62    put(p, i, j);
63    if (get(rank, i) == get(rank, j))
64      put(rank, j, get(rank, j) + 1);
65  }
66
67
68// normalize components has the following postcondidition:
69// i >= p[i]
70// that is, the representative is the node with the smallest index in its class
71// as its precondition it it assumes that the node container is compressed
72
73template <class ParentPA, class Vertex>
74inline void
75normalize_node(ParentPA p, Vertex i)
76{
77  if (i > get(p,i) || get(p, get(p,i)) != get(p,i))   
78    put(p,i, get(p, get(p,i)));
79  else {
80    put(p, get(p,i), i);
81    put(p, i, i);
82  }
83}
84
85  } // namespace detail
86} // namespace boost
87
88#endif // BOOST_DETAIL_DISJOINT_SETS_HPP
Note: See TracBrowser for help on using the repository browser.