SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
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 }
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:219
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:224
Definition: dt.h:1134
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:222
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