SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
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>

Collaboration diagram for TUnionFind:

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

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: