TUnionFind Class Reference

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

#include <gbase.h>

Collaboration diagram for TUnionFind:

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

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 214 of file gbase.h.

Constructor & Destructor Documentation

TUnionFind::TUnionFind ( )

inline

Definition at line 223 of file gbase.h.

: KIdSetH() { }

TUnionFind::TUnionFind ( const int &  ExpectKeys )

inline

Constructor that reserves enough memory for ExpectKeys elements.

Definition at line 225 of file gbase.h.

: KIdSetH(ExpectKeys, true) { }

TUnionFind::TUnionFind ( const TUnionFind &  UnionFind )

inline

Definition at line 226 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 238 of file gbase.h.

References THash< TKey, TDat, THashFunc >::AddDat(), and KIdSetH.

Referenced by TSnap::TSnapDetail::TCNMQMatrix::Init().

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

Here is the call graph for this function:

Here is the caller graph for this function:

void TUnionFind::Dump

(

)

Prints out the structure to standard output.

Definition at line 53 of file gbase.cpp.

References Find(), THash< TKey, TDat, THashFunc >::GetKey(), KIdSetH, and THash< TKey, TDat, THashFunc >::Len().

                      {
  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");
}

Here is the call graph for this function:

int TUnionFind::Find

(

const int &

Key

)

Returns the set that contains element Key.

Definition at line 23 of file gbase.cpp.

References Parent().

Referenced by TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN(), Dump(), IsSameSet(), and Union().

                                   {
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TUnionFind::GetKeyI ( const int &  KeyN ) const

inline

Returns the element KeyN.

Definition at line 234 of file gbase.h.

References THash< TKey, TDat, THashFunc >::GetKey(), and KIdSetH.

{ return KIdSetH.GetKey(KeyN); }

Here is the call graph for this function:

bool TUnionFind::IsKey ( const int &  Key ) const

inline

Returns true if the structure contains element Key.

Definition at line 232 of file gbase.h.

References THash< TKey, TDat, THashFunc >::IsKey(), and KIdSetH.

{ return KIdSetH.IsKey(Key); }

Here is the call graph for this function:

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 242 of file gbase.h.

References Find().

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

Here is the call graph for this function:

int TUnionFind::Len ( ) const

inline

Returns the number of elements in the structure.

Definition at line 230 of file gbase.h.

References KIdSetH, and THash< TKey, TDat, THashFunc >::Len().

{ return KIdSetH.Len(); }

Here is the call graph for this function:

TUnionFind& TUnionFind::operator= ( const TUnionFind &  UF )

inline

Definition at line 227 of file gbase.h.

References KIdSetH.

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

TInt& TUnionFind::Parent ( const int &  Key )

inline

Returns the parent of element Key.

Definition at line 219 of file gbase.h.

References THash< TKey, TDat, THashFunc >::GetDat(), KIdSetH, and TPair< TVal1, TVal2 >::Val1.

Referenced by Find(), and Union().

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

Here is the call graph for this function:

Here is the caller graph for this function:

TInt& TUnionFind::Rank ( const int &  Key )

inline

Returns the rank of element Key.

Definition at line 221 of file gbase.h.

References THash< TKey, TDat, THashFunc >::GetDat(), KIdSetH, and TPair< TVal1, TVal2 >::Val2.

Referenced by Union().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Merges sets with elements Key1 and Key2.

Definition at line 40 of file gbase.cpp.

References Find(), Parent(), and Rank().

Referenced by TSnap::TSnapDetail::TCNMQMatrix::MergeBestQ().

                                                       {
  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)++;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

THash<TInt, TIntPr> TUnionFind::KIdSetH

private

Definition at line 216 of file gbase.h.

Referenced by Add(), Dump(), GetKeyI(), IsKey(), Len(), operator=(), Parent(), and Rank().

---

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

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