TUnionFind Class Reference

Union Find class (Disjoint-set data structure). More...

#include <gbase.h>

List of all members.

Public Member Functions
TInt &	Parent (const int &Key)
	Returns the parent of element Key.
TInt &	Rank (const int &Key)
	Returns the rank of element Key.
	TUnionFind ()
	TUnionFind (const int &ExpectKeys)
	Constructor that reserves enough memory for ExpectKeys elements.
	TUnionFind (const TUnionFind &UnionFind)
TUnionFind &	operator= (const TUnionFind &UF)
int	Len () const
	Returns the number of elements in the structure.
bool	IsKey (const int &Key) const
	Returns true if the structure contains element Key.
int	GetKeyI (const int &KeyN) const
	Returns the element KeyN.
int	Find (const int &Key)
	Returns the set that contains element Key.
int	Add (const int &Key)
	Adds an element Key to the structure.
void	Union (const int &Key1, const int &Key2)
	Merges sets with elements Key1 and Key2.
bool	IsSameSet (const int &Key1, const int &Key2)
	Returns true if elements Key1 and Key2 are in the same set.
void	Dump ()
	Prints out the structure to standard output.
Private Attributes
THash< TInt, TIntPr >	KIdSetH

---

Detailed Description

Union Find class (Disjoint-set data structure).

For more info see: http://en.wikipedia.org/wiki/Disjoint-set_data_structure).

Definition at line 189 of file gbase.h.

---

Constructor & Destructor Documentation

TUnionFind::TUnionFind

(

)

[inline]

Definition at line 198 of file gbase.h.

: KIdSetH() { }

TUnionFind::TUnionFind

(

const int &

ExpectKeys

)

[inline]

Constructor that reserves enough memory for ExpectKeys elements.

Definition at line 200 of file gbase.h.

: KIdSetH(ExpectKeys, true) { }

TUnionFind::TUnionFind

(

const TUnionFind &

UnionFind

)

[inline]

Definition at line 201 of file gbase.h.

: KIdSetH(UnionFind.KIdSetH) { }

---

Member Function Documentation

int TUnionFind::Add

(

const int &

Key

)

[inline]

Adds an element Key to the structure.

Definition at line 213 of file gbase.h.

{ KIdSetH.AddDat(Key, TIntPr(-1, 0));  return Key; }

void TUnionFind::Dump

(

)

Prints out the structure to standard output.

Definition at line 53 of file gbase.cpp.

                      {
  printf("  key\tset\n");
  for (int i = 0; i < KIdSetH.Len(); i++) {
    printf("  %d\t%d\n", int(KIdSetH.GetKey(i)), Find(KIdSetH.GetKey(i)));
  }
  printf("\n");
}

int TUnionFind::Find

(

const int &

Key

)

Returns the set that contains element Key.

Definition at line 23 of file gbase.cpp.

                                   {
  int SetId = Key, parent = Parent(Key);
  // find set id
  while (parent != -1) {
    SetId = parent;
    parent = Parent(parent);
  }
  // flatten
  parent = Key;
  while (parent != -1) {
    const int tmp = Parent(parent);
    if (tmp != -1) { Parent(parent) = SetId; }
    parent = tmp;
  }
  return SetId;
}

int TUnionFind::GetKeyI

(

const int &

KeyN

)

const [inline]

Returns the element KeyN.

Definition at line 209 of file gbase.h.

{ return KIdSetH.GetKey(KeyN); }

bool TUnionFind::IsKey

(

const int &

Key

)

const [inline]

Returns true if the structure contains element Key.

Definition at line 207 of file gbase.h.

{ return KIdSetH.IsKey(Key); }

bool TUnionFind::IsSameSet	(	const int &	Key1,
		const int &	Key2
	)		[inline]

Returns true if elements Key1 and Key2 are in the same set.

Definition at line 217 of file gbase.h.

                                                   {
    return Find(Key1) == Find(Key2); }

int TUnionFind::Len

(

)

const [inline]

Returns the number of elements in the structure.

Definition at line 205 of file gbase.h.

{ return KIdSetH.Len(); }

TUnionFind& TUnionFind::operator=

(

const TUnionFind &

UF

)

[inline]

Definition at line 202 of file gbase.h.

{ KIdSetH=UF.KIdSetH; return *this; }

TInt& TUnionFind::Parent

(

const int &

Key

)

[inline]

Returns the parent of element Key.

Definition at line 194 of file gbase.h.

{ return KIdSetH.GetDat(Key).Val1; }

TInt& TUnionFind::Rank

(

const int &

Key

)

[inline]

Returns the rank of element Key.

Definition at line 196 of file gbase.h.

{ return KIdSetH.GetDat(Key).Val2; }

void TUnionFind::Union	(	const int &	Key1,
		const int &	Key2
	)

Merges sets with elements Key1 and Key2.

Definition at line 40 of file gbase.cpp.

                                                       {
  const int root1 = Find(Key1);
  const int root2 = Find(Key2);
  TInt& rank1 = Rank(root1);
  TInt& rank2 = Rank(root2);
  if (rank1 > rank2) { Parent(root2) = root1; }
  else if (rank1 < rank2) { Parent(root1) = root2; }
  else if (root1 != root2) {
    Parent(root2) = root1;
    Rank(root1)++;
  }
}

---

Member Data Documentation

THash<TInt, TIntPr> TUnionFind::KIdSetH [private]

Definition at line 191 of file gbase.h.

---

The documentation for this class was generated from the following files:

• snap-core/gbase.h
• snap-core/gbase.cpp