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
gbase.cpp
Go to the documentation of this file.
00001 
00002 // Graph Base
00003 namespace TSnap {
00004 
00005 TStr GetFlagStr(const TGraphFlag& GraphFlag) {
00006   switch (GraphFlag) {
00007     case gfUndef : return "Undef";
00008     case gfDirected : return "Directed";
00009     case gfMultiGraph : return "Multigraph";
00010     case gfNodeDat : return "NodeDat";
00011     case gfEdgeDat : return "EdgeDat";
00012     case gfSources : return "Sources";
00013     case gfBipart : return "Bipartite";
00014     default: FailR("Unknown graph type");
00015   };
00016   return TStr();
00017 }
00018 
00019 };  // namespace TSnap
00020 
00022 // Union Find
00023 int TUnionFind::Find(const int& Key) {
00024   int SetId = Key, parent = Parent(Key);
00025   // find set id
00026   while (parent != -1) {
00027     SetId = parent;
00028     parent = Parent(parent);
00029   }
00030   // flatten
00031   parent = Key;
00032   while (parent != -1) {
00033     const int tmp = Parent(parent);
00034     if (tmp != -1) { Parent(parent) = SetId; }
00035     parent = tmp;
00036   }
00037   return SetId;
00038 }
00039 
00040 void TUnionFind::Union(const int& Key1, const int& Key2) {
00041   const int root1 = Find(Key1);
00042   const int root2 = Find(Key2);
00043   TInt& rank1 = Rank(root1);
00044   TInt& rank2 = Rank(root2);
00045   if (rank1 > rank2) { Parent(root2) = root1; }
00046   else if (rank1 < rank2) { Parent(root1) = root2; }
00047   else if (root1 != root2) {
00048     Parent(root2) = root1;
00049     Rank(root1)++;
00050   }
00051 }
00052 
00053 void TUnionFind::Dump() {
00054   printf("  key\tset\n");
00055   for (int i = 0; i < KIdSetH.Len(); i++) {
00056     printf("  %d\t%d\n", int(KIdSetH.GetKey(i)), Find(KIdSetH.GetKey(i)));
00057   }
00058   printf("\n");
00059 }