← Back to branch summary

~ubuntu-branches/ubuntu/warty/aqsis/warty

« back to all changes in this revision

Viewing changes to boost/boost/pending/detail/disjoint_sets.hpp

  • Committer: Bazaar Package Importer
  • Author(s): LaMont Jones
  • Date: 2004-08-24 07:25:04 UTC
  • Revision ID: james.westby@ubuntu.com-20040824072504-zf993vnevvisdsvb
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

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