SNAP Library 2.4, Developer Reference  2015-05-11 19:40:56
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
TUnionFind Class Reference

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

#include <gbase.h>

Collaboration diagram for TUnionFind:

Public Member Functions

TIntParent (const int &Key)
 Returns the parent of element Key. More...
 
TIntRank (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)
 
TUnionFindoperator= (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, TIntPrKIdSetH
 

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.

223 : KIdSetH() { }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
TUnionFind::TUnionFind ( const int &  ExpectKeys)
inline

Constructor that reserves enough memory for ExpectKeys elements.

Definition at line 225 of file gbase.h.

225 : KIdSetH(ExpectKeys, true) { }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
TUnionFind::TUnionFind ( const TUnionFind UnionFind)
inline

Definition at line 226 of file gbase.h.

226 : KIdSetH(UnionFind.KIdSetH) { }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216

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

238 { KIdSetH.AddDat(Key, TIntPr(-1, 0)); return Key; }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
TDat & AddDat(const TKey &Key)
Definition: hash.h:196

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

53  {
54  printf(" key\tset\n");
55  for (int i = 0; i < KIdSetH.Len(); i++) {
56  printf(" %d\t%d\n", int(KIdSetH.GetKey(i)), Find(KIdSetH.GetKey(i)));
57  }
58  printf("\n");
59 }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
int Find(const int &Key)
Returns the set that contains element Key.
Definition: gbase.cpp:23
int Len() const
Definition: hash.h:186
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210

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

23  {
24  int SetId = Key, parent = Parent(Key);
25  // find set id
26  while (parent != -1) {
27  SetId = parent;
28  parent = Parent(parent);
29  }
30  // flatten
31  parent = Key;
32  while (parent != -1) {
33  const int tmp = Parent(parent);
34  if (tmp != -1) { Parent(parent) = SetId; }
35  parent = tmp;
36  }
37  return SetId;
38 }
TInt & Parent(const int &Key)
Returns the parent of element Key.
Definition: gbase.h:219

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.

234 { return KIdSetH.GetKey(KeyN); }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210

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.

232 { return KIdSetH.IsKey(Key); }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
bool IsKey(const TKey &Key) const
Definition: hash.h:216

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

242  {
243  return Find(Key1) == Find(Key2); }
int Find(const int &Key)
Returns the set that contains element Key.
Definition: gbase.cpp:23

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

230 { return KIdSetH.Len(); }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
int Len() const
Definition: hash.h:186

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.

227 { KIdSetH=UF.KIdSetH; return *this; }
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
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().

219 { return KIdSetH.GetDat(Key).Val1; }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
TVal1 Val1
Definition: ds.h:34

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

221 { return KIdSetH.GetDat(Key).Val2; }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
TVal2 Val2
Definition: ds.h:35

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

40  {
41  const int root1 = Find(Key1);
42  const int root2 = Find(Key2);
43  TInt& rank1 = Rank(root1);
44  TInt& rank2 = Rank(root2);
45  if (rank1 > rank2) { Parent(root2) = root1; }
46  else if (rank1 < rank2) { Parent(root1) = root2; }
47  else if (root1 != root2) {
48  Parent(root2) = root1;
49  Rank(root1)++;
50  }
51 }
int Find(const int &Key)
Returns the set that contains element Key.
Definition: gbase.cpp:23
TInt & Rank(const int &Key)
Returns the rank of element Key.
Definition: gbase.h:221
Definition: dt.h:1042
TInt & Parent(const int &Key)
Returns the parent of element Key.
Definition: gbase.h:219

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: