SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
gbase.cpp
Go to the documentation of this file.
1 // Graph Base
3 namespace TSnap {
4 
5 TStr GetFlagStr(const TGraphFlag& GraphFlag) {
6  switch (GraphFlag) {
7  case gfUndef : return "Undef";
8  case gfDirected : return "Directed";
9  case gfMultiGraph : return "Multigraph";
10  case gfNodeDat : return "NodeDat";
11  case gfEdgeDat : return "EdgeDat";
12  case gfSources : return "Sources";
13  case gfBipart : return "Bipartite";
14  default: FailR("Unknown graph type");
15  };
16  return TStr();
17 }
18 
19 }; // namespace TSnap
20 
22 // Union Find
23 int TUnionFind::Find(const int& Key) {
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 }
39 
40 void TUnionFind::Union(const int& Key1, const int& Key2) {
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 }
52 
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 }
Main namespace for all the Snap global entities.
Definition: alg.h:1
void Union(const int &Key1, const int &Key2)
Merges sets with elements Key1 and Key2.
Definition: gbase.cpp:40
default value, no flags
Definition: gbase.h:12
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
TStr GetFlagStr(const TGraphFlag &GraphFlag)
Returns a string representation of a flag.
Definition: gbase.cpp:5
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:232
int Find(const int &Key)
Returns the set that contains element Key.
Definition: gbase.cpp:23
network with data on edges
Definition: gbase.h:16
#define FailR(Reason)
Definition: bd.h:240
TInt & Rank(const int &Key)
Returns the rank of element Key.
Definition: gbase.h:237
Definition: dt.h:1137
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
void Dump()
Prints out the structure to standard output.
Definition: gbase.cpp:53
Definition: dt.h:412
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
TInt & Parent(const int &Key)
Returns the parent of element Key.
Definition: gbase.h:235
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
network with data on nodes
Definition: gbase.h:15
int Len() const
Definition: hash.h:228
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
bipartite graph
Definition: gbase.h:18