SNAP Library 2.1, User Reference  2013-09-25 10:47:25
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
TUnionFind Class Reference

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

#include <gbase.h>

List of all members.

Public Member Functions

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

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

{ 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 234 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 232 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 242 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 230 of file gbase.h.

{ return KIdSetH.Len(); }
TUnionFind& TUnionFind::operator= ( const TUnionFind UF) [inline]

Definition at line 227 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 219 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 221 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

Definition at line 216 of file gbase.h.


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