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.
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.

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 209 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 207 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 217 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 205 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 202 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 194 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 196 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 191 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

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation