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.h
Go to the documentation of this file.
1 // Defines
3 #define Kilo(n) (1000*(n))
4 #define Mega(n) (1000*1000*(n))
5 #define Giga(n) (1000*1000*1000*(n))
6 
7 //#//////////////////////////////////////////////
9 
11 typedef enum TGraphFlag_ {
12  gfUndef=0,
20 } TGraphFlag;
21 
24 
25 namespace TSnap {
26 
28 template <class TGraph> struct IsDirected { enum { Val = 0 }; };
30 template <class TGraph> struct IsMultiGraph { enum { Val = 0 }; };
32 template <class TGraph> struct IsNodeDat { enum { Val = 0 }; };
34 template <class TGraph> struct IsEdgeDat { enum { Val = 0 }; };
36 template <class TGraph> struct IsSources { enum { Val = 0 }; };
38 template <class TGraph> struct IsBipart { enum { Val = 0 }; };
39 
41 #define HasGraphFlag(TGraph, Flag) \
42  ((Flag)==gfDirected ? TSnap::IsDirected<TGraph::TNet>::Val : \
43  (Flag)==gfMultiGraph ? TSnap::IsMultiGraph<TGraph::TNet>::Val : \
44  (Flag)==gfNodeDat ? TSnap::IsNodeDat<TGraph::TNet>::Val : \
45  (Flag)==gfEdgeDat ? TSnap::IsEdgeDat<TGraph::TNet>::Val : \
46  (Flag)==gfSources ? TSnap::IsSources<TGraph::TNet>::Val : \
47  (Flag)==gfBipart ? TSnap::IsBipart<TGraph::TNet>::Val : 0)
48 
49 #if 0
50 // RS 2013/08/19, commented out IsDerivedFrom, it is not called anywhere
51 // swig throws an error
53 template<class TDerivClass, class TBaseClass>
54 class IsDerivedFrom {
55 private:
56  struct Yes { char a[1]; };
57  struct No { char a[10]; };
58  static Yes Test(TBaseClass*);
59  static No Test(...); // undefined
60 public:
61  enum { Val = sizeof(Test(static_cast<TDerivClass*>(0))) == sizeof(Yes) ? 1 : 0 };
62 };
63 #endif
64 
66 // Graph Base
67 
69 TStr GetFlagStr(const TGraphFlag& GraphFlag);
71 
73 template <class PGraph> void PrintInfo(const PGraph& Graph, const TStr& Desc="", const TStr& OutFNm="", const bool& Fast=true);
74 
76 // Implementation
77 
78 // Forward declaration, definition in triad.h
79 template <class PGraph> int64 GetTriads(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes=-1);
80 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam);
81 template <class PGraph> double GetMxWccSz(const PGraph& Graph);
82 template <class PGraph> double GetMxSccSz(const PGraph& Graph);
83 template<class PGraph> int GetKCoreNodes(const PGraph& Graph, TIntPrV& CoreIdSzV);
84 template<class PGraph> int GetKCoreEdges(const PGraph& Graph, TIntPrV& CoreIdSzV);
85 
86 template <class PGraph>
87 void PrintInfo(const PGraph& Graph, const TStr& Desc, const TStr& OutFNm, const bool& Fast) {
88  int BiDirEdges=0, ZeroNodes=0, ZeroInNodes=0, ZeroOutNodes=0, SelfEdges=0, NonZIODegNodes=0;
89  THash<TIntPr, TInt> UniqDirE, UniqUnDirE;
90  FILE *F = stdout;
91  if (! OutFNm.Empty()) F = fopen(OutFNm.CStr(), "wt");
92  if (! Desc.Empty()) { fprintf(F, "%s:", Desc.CStr()); }
93  else { fprintf(F, "Graph:"); }
94  for (int f = gfUndef; f < gfMx; f++) {
95  if (HasGraphFlag(typename PGraph::TObj, TGraphFlag(f))) {
96  fprintf(F, " %s", TSnap::GetFlagStr(TGraphFlag(f)).CStr()); }
97  }
98  // calc stat
99  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
100  if (NI.GetDeg()==0) ZeroNodes++;
101  if (NI.GetInDeg()==0) ZeroInNodes++;
102  if (NI.GetOutDeg()==0) ZeroOutNodes++;
103  if (NI.GetInDeg()!=0 && NI.GetOutDeg()!=0) NonZIODegNodes++;
104  if (! Fast || Graph->GetNodes() < 1000) {
105  const int NId = NI.GetId();
106  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
107  const int DstNId = NI.GetOutNId(edge);
108  if (Graph->IsEdge(DstNId, NId)) BiDirEdges++;
109  if (NId == DstNId) SelfEdges++;
110  UniqDirE.AddKey(TIntPr(NId, DstNId));
111  UniqUnDirE.AddKey(TIntPr(TInt::GetMn(NId, DstNId), TInt::GetMx(NId, DstNId)));
112  }
113  }
114  }
115  int64 Closed=0, Open=0;
116  double WccSz=0, SccSz=0;
117  double EffDiam=0;
118  int FullDiam=0;
119  if (! Fast) {
120  TSnap::GetTriads(Graph, Closed, Open);
121  WccSz = TSnap::GetMxWccSz(Graph);
122  SccSz = TSnap::GetMxSccSz(Graph);
123  TSnap::GetBfsEffDiam(Graph, 100, false, EffDiam, FullDiam);
124  }
125  // print info
126  fprintf(F, "\n");
127  fprintf(F, " Nodes: %d\n", Graph->GetNodes());
128  fprintf(F, " Edges: %d\n", Graph->GetEdges());
129  fprintf(F, " Zero Deg Nodes: %d\n", ZeroNodes);
130  fprintf(F, " Zero InDeg Nodes: %d\n", ZeroInNodes);
131  fprintf(F, " Zero OutDeg Nodes: %d\n", ZeroOutNodes);
132  fprintf(F, " NonZero In-Out Deg Nodes: %d\n", NonZIODegNodes);
133  if (! Fast) {
134  fprintf(F, " Unique directed edges: %d\n", UniqDirE.Len());
135  fprintf(F, " Unique undirected edges: %d\n", UniqUnDirE.Len());
136  fprintf(F, " Self Edges: %d\n", SelfEdges);
137  fprintf(F, " BiDir Edges: %d\n", BiDirEdges);
138  fprintf(F, " Closed triangles: %s\n", TUInt64::GetStr(Closed).CStr());
139  fprintf(F, " Open triangles: %s\n", TUInt64::GetStr(Open).CStr());
140  fprintf(F, " Frac. of closed triads: %f\n", Closed/double(Closed+Open));
141  fprintf(F, " Connected component size: %f\n", WccSz);
142  fprintf(F, " Strong conn. comp. size: %f\n", SccSz);
143  fprintf(F, " Approx. full diameter: %d\n", FullDiam);
144  fprintf(F, " 90%% effective diameter: %f\n", EffDiam);
145  //fprintf(F, " Core\tNodes\tEdges\n");
146  //for (int i = 0; i < CNodesV.Len(); i++) {
147  // printf(" %d\t%d\t%d\n", CNodesV[i].Val1(), CNodesV[i].Val2(), CEdgesV[i].Val2());
148  //}
149  }
150  if (! OutFNm.Empty()) { fclose(F); }
151 }
152 
153 } // namespace TSnap
154 
155 //#//////////////////////////////////////////////
157 template <class TVal>
158 class TSnapQueue {
159 private:
160  TInt MxFirst; // how often we move the queue to the start of the array
163 public:
164  TSnapQueue() : MxFirst(1024), First(0), Last(0), ValV(MxFirst, 0) { }
166  TSnapQueue(const int& MxVals) : MxFirst(1024+MxVals/10), First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
167  TSnapQueue(const int& MxVals, const int& MaxFirst) : MxFirst(MaxFirst),
168  First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
169  TSnapQueue(const TSnapQueue& Queue) : MxFirst(Queue.MxFirst), First(Queue.First), Last(Queue.Last), ValV(Queue.ValV) { }
171  explicit TSnapQueue(TSIn& SIn): MxFirst(SIn), First(SIn), Last(SIn), ValV(SIn) { }
173  void Save(TSOut& SOut) const { MxFirst.Save(SOut); First.Save(SOut); Last.Save(SOut); ValV.Save(SOut); }
174 
175  TSnapQueue& operator=(const TSnapQueue& Queue) { if (this != &Queue) { MxFirst=Queue.MxFirst;
176  First=Queue.First; Last=Queue.Last; ValV=Queue.ValV; } return *this; }
178  const TVal& operator[](const int& ValN) const { return ValV[First+ValN]; }
179 
181  void Clr(const bool& DoDel=true) { ValV.Clr(DoDel); First=Last=0; }
182  void Gen(const int& MxVals, const int& MaxFirst=1024) {
183  MxFirst=MaxFirst; First=Last=0; ValV.Gen(MxVals, 0); }
184 
186  bool Empty() const {return First==Last;}
188  int Len() const {return Last-First;}
190  int GetFirst() const { return First; }
192  int GetLast() const { return Last; }
193  int Reserved() const { return ValV.Reserved(); }
194 
196  const TVal& Top() const { return ValV[First]; }
198  void Pop() { First++;
199  if (First==Last) { ValV.Clr(false); First=Last=0; } }
201  void Push(const TVal& Val) {
202  if (First>0 && (First > MxFirst || ValV.Len() == ValV.Reserved()) && ! ValV.Empty()) {
203  //printf("[move cc queue.Len:%d-->%d]", ValV.Len(),Len()); TExeTm Tm;
204  memmove(ValV.BegI(), ValV.GetI(First), sizeof(TVal)*Len());
205  ValV.Del(Len(), ValV.Len()-1); Last-=First; First=0;
206  //printf("[%s]\n", Tm.GetStr()); fflush(stdout);
207  }
208  //if (ValV.Len() == ValV.Reserved()){ printf("[resizeCCQ]"); fflush(stdout); }
209  Last++; ValV.Add(Val);
210  }
211 };
212 
213 //#//////////////////////////////////////////////
215 
217 class TUnionFind {
218 private:
219  THash<TInt, TIntPr> KIdSetH; // key id to (parent, rank)
220 public:
222  TInt& Parent(const int& Key) { return KIdSetH.GetDat(Key).Val1; }
224  TInt& Rank(const int& Key) { return KIdSetH.GetDat(Key).Val2; }
225 public:
226  TUnionFind() : KIdSetH() { }
228  TUnionFind(const int& ExpectKeys) : KIdSetH(ExpectKeys, true) { }
229  TUnionFind(const TUnionFind& UnionFind) : KIdSetH(UnionFind.KIdSetH) { }
230  TUnionFind& operator = (const TUnionFind& UF) { KIdSetH=UF.KIdSetH; return *this; }
231 
233  int Len() const { return KIdSetH.Len(); }
235  bool IsKey(const int& Key) const { return KIdSetH.IsKey(Key); }
237  int GetKeyI(const int& KeyN) const { return KIdSetH.GetKey(KeyN); }
239  int Find(const int& Key);
241  int Add(const int& Key) { KIdSetH.AddDat(Key, TIntPr(-1, 0)); return Key; }
243  void Union(const int& Key1, const int& Key2);
245  bool IsSameSet(const int& Key1, const int& Key2) {
246  return Find(Key1) == Find(Key2); }
248  void Dump();
249 };
250 
251 //#//////////////////////////////////////////////
253 
255 template <class TVal, class TCmp = TLss<TVal> >
256 class THeap {
257 private:
260 private:
261  void PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val);
262  void AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val);
263  void MakeHeap(const int& First, const int& Len);
264 public:
265  THeap() : HeapV() { }
266  THeap(const int& MxVals) : Cmp(), HeapV(MxVals, 0) { }
267  THeap(const TCmp& _Cmp) : Cmp(_Cmp), HeapV() { }
268  THeap(const TVec<TVal>& Vec) : Cmp(), HeapV(Vec) { MakeHeap(); }
269  THeap(const TVec<TVal>& Vec, const TCmp& _Cmp) : Cmp(_Cmp), HeapV(Vec) { MakeHeap(); }
270  THeap(const THeap& Heap) : Cmp(Heap.Cmp), HeapV(Heap.HeapV) { }
271  THeap& operator = (const THeap& H) { Cmp=H.Cmp; HeapV=H.HeapV; return *this; }
272 
274  const TVal& TopHeap() const { return HeapV[0]; }
276  void PushHeap(const TVal& Val);
278  TVal PopHeap();
280  int Len() const { return HeapV.Len(); }
282  bool Empty() const { return HeapV.Empty(); }
284  const TVec<TVal>& operator()() const { return HeapV; }
286  TVec<TVal>& operator()() { return HeapV; }
288  void Add(const TVal& Val) { HeapV.Add(Val); }
290  void MakeHeap() { MakeHeap(0, Len()); }
291 };
292 
293 template <class TVal, class TCmp>
294 void THeap<TVal, TCmp>::PushHeap(const TVal& Val) {
295  HeapV.Add(Val);
296  PushHeap(0, HeapV.Len()-1, 0, Val);
297 }
298 
299 template <class TVal, class TCmp>
301  IAssert(! HeapV.Empty());
302  const TVal Top = HeapV[0];
303  HeapV[0] = HeapV.Last();
304  HeapV.DelLast();
305  if (! HeapV.Empty()) {
306  AdjustHeap(0, 0, HeapV.Len(), HeapV[0]);
307  }
308  return Top;
309 }
310 
311 template <class TVal, class TCmp>
312 void THeap<TVal, TCmp>::PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val) {
313  int Parent = (HoleIdx-1)/2;
314  while (HoleIdx > Top && Cmp(HeapV[First+Parent], Val)) {
315  HeapV[First+HoleIdx] = HeapV[First+Parent];
316  HoleIdx = Parent; Parent = (HoleIdx-1)/2;
317  }
318  HeapV[First+HoleIdx] = Val;
319 }
320 
321 template <class TVal, class TCmp>
322 void THeap<TVal, TCmp>::AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val) {
323  const int Top = HoleIdx;
324  int Right = 2*HoleIdx+2;
325  while (Right < Len) {
326  if (Cmp(HeapV[First+Right], HeapV[First+Right-1])) { Right--; }
327  HeapV[First+HoleIdx] = HeapV[First+Right];
328  HoleIdx = Right; Right = 2*(Right+1); }
329  if (Right == Len) {
330  HeapV[First+HoleIdx] = HeapV[First+Right-1];
331  HoleIdx = Right-1; }
332  PushHeap(First, HoleIdx, Top, Val);
333 }
334 
335 template <class TVal, class TCmp>
336 void THeap<TVal, TCmp>::MakeHeap(const int& First, const int& Len) {
337  if (Len < 2) { return; }
338  int Parent = (Len-2)/2;
339  while (true) {
340  AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
341  if (Parent == 0) { return; }
342  Parent--;
343  }
344 }
345 
int GetLast() const
Returns the location of the last element in the queue.
Definition: gbase.h:192
THeap(const THeap &Heap)
Definition: gbase.h:270
#define IAssert(Cond)
Definition: bd.h:262
TVec< TVal > HeapV
Definition: gbase.h:259
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Tests (at compile time) if the graph is a network with data on nodes.
Definition: gbase.h:32
int64 GetTriads(const PGraph &Graph, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:207
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
void MakeHeap()
Builds a heap from a set of elements.
Definition: gbase.h:290
TVec< TVal > ValV
Definition: gbase.h:162
int GetKCoreNodes(const PGraph &Graph, TIntPrV &CoreIdSzV)
Returns the number of nodes in each core of order K (where K=0, 1, ...)
Definition: kcore.h:114
int Add(const int &Key)
Adds an element Key to the structure.
Definition: gbase.h:241
TCmp Cmp
Definition: gbase.h:258
enum TAttrType_ TAttrType
Types for tables, sparse and dense attributes.
TSnapQueue(TSIn &SIn)
Constructor that loads the queue from a (binary) stream SIn.
Definition: gbase.h:171
void Union(const int &Key1, const int &Key2)
Merges sets with elements Key1 and Key2.
Definition: gbase.cpp:40
bool Empty() const
Tests whether the heap is empty.
Definition: gbase.h:282
void Add(const TVal &Val)
Adds an element to the data structure. Heap property is not maintained by Add() and thus after all th...
Definition: gbase.h:288
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
double GetBfsEffDiam(const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
Returns the (approximation of the) Effective Diameter (90-th percentile of the distribution of shorte...
Definition: bfsdfs.h:415
const TVal & TopHeap() const
Returns a reference to the element at the top of the heap (the largest element of the heap)...
Definition: gbase.h:274
TInt First
Definition: gbase.h:161
void Save(TSOut &SOut) const
Definition: dt.h:1150
double GetMxWccSz(const PGraph &Graph)
Returns the fraction of nodes in the largest weakly connected component of a Graph.
Definition: cncom.h:436
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1182
TSnapQueue & operator=(const TSnapQueue &Queue)
Definition: gbase.h:175
Tests (at compile time) if the graph is directed.
Definition: gbase.h:28
const TVal & operator[](const int &ValN) const
Returns the value of the ValN element in the queue, but does not remove the element.
Definition: gbase.h:178
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
default value, no flags
Definition: gbase.h:12
TInt Last
Definition: gbase.h:161
TUnionFind & operator=(const TUnionFind &UF)
Definition: gbase.h:230
void Gen(const int &MxVals, const int &MaxFirst=1024)
Definition: gbase.h:182
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TAttrType_
Types for tables, sparse and dense attributes.
Definition: gbase.h:23
Definition: gbase.h:23
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
void Pop()
Removes the first element from the queue.
Definition: gbase.h:198
TStr GetFlagStr(const TGraphFlag &GraphFlag)
Returns a string representation of a flag.
Definition: gbase.cpp:5
THeap(const int &MxVals)
Definition: gbase.h:266
THeap()
Definition: gbase.h:265
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:186
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:219
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
bool IsKey(const int &Key) const
Returns true if the structure contains element Key.
Definition: gbase.h:235
int Find(const int &Key)
Returns the set that contains element Key.
Definition: gbase.cpp:23
static int GetMn(const int &Int1, const int &Int2)
Definition: dt.h:1180
THeap(const TCmp &_Cmp)
Definition: gbase.h:267
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
Tests (at compile time) if the graph is a network with data on edges.
Definition: gbase.h:34
int GetKeyI(const int &KeyN) const
Returns the element KeyN.
Definition: gbase.h:237
network with data on edges
Definition: gbase.h:16
double GetMxSccSz(const PGraph &Graph)
Returns the fraction of nodes in the largest strongly connected component of a Graph.
Definition: cncom.h:444
Simple heap data structure.
Definition: gbase.h:256
Definition: bd.h:402
THeap(const TVec< TVal > &Vec, const TCmp &_Cmp)
Definition: gbase.h:269
Tests (at compile time) if the graph is a multigraph with multiple edges between the same nodes...
Definition: gbase.h:30
int GetKCoreEdges(const PGraph &Graph, TIntPrV &CoreIdSzV)
Returns the number of edges in each core of order K (where K=0, 1, ...)
Definition: kcore.h:126
TInt MxFirst
Definition: gbase.h:160
TUnionFind(const TUnionFind &UnionFind)
Definition: gbase.h:229
const TVec< TVal > & operator()() const
Returns a reference to the vector containing the elements of the heap.
Definition: gbase.h:284
int Len() const
Returns the number of elements in the structure.
Definition: gbase.h:233
int Len() const
Returns the number of elements in the queue.
Definition: gbase.h:188
Definition: fl.h:128
TInt & Rank(const int &Key)
Returns the rank of element Key.
Definition: gbase.h:224
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:181
Definition: dt.h:1134
int GetFirst() const
Returns the location of the first element in the queue.
Definition: gbase.h:190
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TSnapQueue(const int &MxVals)
Constructor that reserves enough memory for a queue with MxVals elements.
Definition: gbase.h:166
TSnapQueue()
Definition: gbase.h:164
int AddKey(const TKey &Key)
Definition: hash.h:373
void Dump()
Prints out the structure to standard output.
Definition: gbase.cpp:53
TStr GetStr() const
Definition: dt.h:1360
int Reserved() const
Definition: gbase.h:193
long long int64
Definition: bd.h:27
Definition: dt.h:412
bool Empty() const
Definition: dt.h:488
sentinel, last value for iteration
Definition: gbase.h:19
void PushHeap(const int &First, int HoleIdx, const int &Top, TVal Val)
Definition: gbase.h:312
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:201
THeap & operator=(const THeap &H)
Definition: gbase.h:271
TUnionFind()
Definition: gbase.h:226
Definition: gbase.h:23
Fast Queue used by the TBreathFS (uses memcpy to move objects TVal around).
Definition: gbase.h:158
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
TVal1 Val1
Definition: ds.h:34
bool IsSameSet(const int &Key1, const int &Key2)
Returns true if elements Key1 and Key2 are in the same set.
Definition: gbase.h:245
TVal2 Val2
Definition: ds.h:35
TUnionFind(const int &ExpectKeys)
Constructor that reserves enough memory for ExpectKeys elements.
Definition: gbase.h:228
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:196
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVal PopHeap()
Removes the top element from the heap.
Definition: gbase.h:300
Tests (at compile time) if the nodes store only out-edges, but not in-edges.
Definition: gbase.h:36
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
void AdjustHeap(const int &First, int HoleIdx, const int &Len, TVal Val)
Definition: gbase.h:322
Definition: gbase.h:23
network with data on nodes
Definition: gbase.h:15
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:280
char * CStr()
Definition: dt.h:476
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TIter GetI(const TSizeTy &ValN) const
Returns an iterator an element at position ValN.
Definition: ds.h:597
TGraphFlag_
Graph Flags, used for quick testing of graph types.
Definition: gbase.h:11
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
Tests (at compile time) if the graph is a bipartite graph type.
Definition: gbase.h:38
TSnapQueue(const TSnapQueue &Queue)
Definition: gbase.h:169
Union Find class (Disjoint-set data structure).
Definition: gbase.h:217
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
TVec< TVal > & operator()()
Returns a reference to the vector containing the elements of the heap.
Definition: gbase.h:286
bipartite graph
Definition: gbase.h:18
TSnapQueue(const int &MxVals, const int &MaxFirst)
Definition: gbase.h:167
void Save(TSOut &SOut) const
Saves the queue to a (binary) stream SOut.
Definition: gbase.h:173
THeap(const TVec< TVal > &Vec)
Definition: gbase.h:268
void PrintInfo(const PGraph &Graph, const TStr &Desc="", const TStr &OutFNm="", const bool &Fast=true)
Prints basic graph statistics.
Definition: gbase.h:87