SNAP Library 2.3, User Reference  2014-06-16 11:58:46
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 
22 namespace TSnap {
23 
25 template <class TGraph> struct IsDirected { enum { Val = 0 }; };
27 template <class TGraph> struct IsMultiGraph { enum { Val = 0 }; };
29 template <class TGraph> struct IsNodeDat { enum { Val = 0 }; };
31 template <class TGraph> struct IsEdgeDat { enum { Val = 0 }; };
33 template <class TGraph> struct IsSources { enum { Val = 0 }; };
35 template <class TGraph> struct IsBipart { enum { Val = 0 }; };
36 
38 #define HasGraphFlag(TGraph, Flag) \
39  ((Flag)==gfDirected ? TSnap::IsDirected<TGraph::TNet>::Val : \
40  (Flag)==gfMultiGraph ? TSnap::IsMultiGraph<TGraph::TNet>::Val : \
41  (Flag)==gfNodeDat ? TSnap::IsNodeDat<TGraph::TNet>::Val : \
42  (Flag)==gfEdgeDat ? TSnap::IsEdgeDat<TGraph::TNet>::Val : \
43  (Flag)==gfSources ? TSnap::IsSources<TGraph::TNet>::Val : \
44  (Flag)==gfBipart ? TSnap::IsBipart<TGraph::TNet>::Val : 0)
45 
46 #if 0
47 // RS 2013/08/19, commented out IsDerivedFrom, it is not called anywhere
48 // swig throws an error
50 template<class TDerivClass, class TBaseClass>
51 class IsDerivedFrom {
52 private:
53  struct Yes { char a[1]; };
54  struct No { char a[10]; };
55  static Yes Test(TBaseClass*);
56  static No Test(...); // undefined
57 public:
58  enum { Val = sizeof(Test(static_cast<TDerivClass*>(0))) == sizeof(Yes) ? 1 : 0 };
59 };
60 #endif
61 
63 // Graph Base
64 
66 TStr GetFlagStr(const TGraphFlag& GraphFlag);
68 
70 template <class PGraph> void PrintInfo(const PGraph& Graph, const TStr& Desc="", const TStr& OutFNm="", const bool& Fast=true);
71 
73 // Implementation
74 
75 // Forward declaration, definition in triad.h
76 template <class PGraph> int64 GetTriads(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes=-1);
77 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam);
78 template <class PGraph> double GetMxWccSz(const PGraph& Graph);
79 template <class PGraph> double GetMxSccSz(const PGraph& Graph);
80 template<class PGraph> int GetKCoreNodes(const PGraph& Graph, TIntPrV& CoreIdSzV);
81 template<class PGraph> int GetKCoreEdges(const PGraph& Graph, TIntPrV& CoreIdSzV);
82 
83 template <class PGraph>
84 void PrintInfo(const PGraph& Graph, const TStr& Desc, const TStr& OutFNm, const bool& Fast) {
85  int BiDirEdges=0, ZeroNodes=0, ZeroInNodes=0, ZeroOutNodes=0, SelfEdges=0, NonZIODegNodes=0;
86  THash<TIntPr, TInt> UniqDirE, UniqUnDirE;
87  FILE *F = stdout;
88  if (! OutFNm.Empty()) F = fopen(OutFNm.CStr(), "wt");
89  if (! Desc.Empty()) { fprintf(F, "%s:", Desc.CStr()); }
90  else { fprintf(F, "Graph:"); }
91  for (int f = gfUndef; f < gfMx; f++) {
92  if (HasGraphFlag(typename PGraph::TObj, TGraphFlag(f))) {
93  fprintf(F, " %s", TSnap::GetFlagStr(TGraphFlag(f)).CStr()); }
94  }
95  // calc stat
96  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
97  if (NI.GetDeg()==0) ZeroNodes++;
98  if (NI.GetInDeg()==0) ZeroInNodes++;
99  if (NI.GetOutDeg()==0) ZeroOutNodes++;
100  if (NI.GetInDeg()!=0 && NI.GetOutDeg()!=0) NonZIODegNodes++;
101  if (! Fast || Graph->GetNodes() < 1000) {
102  const int NId = NI.GetId();
103  for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
104  const int DstNId = NI.GetOutNId(edge);
105  if (Graph->IsEdge(DstNId, NId)) BiDirEdges++;
106  if (NId == DstNId) SelfEdges++;
107  UniqDirE.AddKey(TIntPr(NId, DstNId));
108  UniqUnDirE.AddKey(TIntPr(TInt::GetMn(NId, DstNId), TInt::GetMx(NId, DstNId)));
109  }
110  }
111  }
112  int64 Closed=0, Open=0;
113  double WccSz=0, SccSz=0;
114  double EffDiam=0;
115  int FullDiam=0;
116  if (! Fast) {
117  TSnap::GetTriads(Graph, Closed, Open);
118  WccSz = TSnap::GetMxWccSz(Graph);
119  SccSz = TSnap::GetMxSccSz(Graph);
120  TSnap::GetBfsEffDiam(Graph, 100, false, EffDiam, FullDiam);
121  }
122  // print info
123  fprintf(F, "\n");
124  fprintf(F, " Nodes: %d\n", Graph->GetNodes());
125  fprintf(F, " Edges: %d\n", Graph->GetEdges());
126  fprintf(F, " Zero Deg Nodes: %d\n", ZeroNodes);
127  fprintf(F, " Zero InDeg Nodes: %d\n", ZeroInNodes);
128  fprintf(F, " Zero OutDeg Nodes: %d\n", ZeroOutNodes);
129  fprintf(F, " NonZero In-Out Deg Nodes: %d\n", NonZIODegNodes);
130  if (! Fast) {
131  fprintf(F, " Unique directed edges: %d\n", UniqDirE.Len());
132  fprintf(F, " Unique undirected edges: %d\n", UniqUnDirE.Len());
133  fprintf(F, " Self Edges: %d\n", SelfEdges);
134  fprintf(F, " BiDir Edges: %d\n", BiDirEdges);
135  fprintf(F, " Closed triangles: %s\n", TUInt64::GetStr(Closed).CStr());
136  fprintf(F, " Open triangles: %s\n", TUInt64::GetStr(Open).CStr());
137  fprintf(F, " Frac. of closed triads: %f\n", Closed/double(Closed+Open));
138  fprintf(F, " Connected component size: %f\n", WccSz);
139  fprintf(F, " Strong conn. comp. size: %f\n", SccSz);
140  fprintf(F, " Approx. full diameter: %d\n", FullDiam);
141  fprintf(F, " 90%% effective diameter: %f\n", EffDiam);
142  //fprintf(F, " Core\tNodes\tEdges\n");
143  //for (int i = 0; i < CNodesV.Len(); i++) {
144  // printf(" %d\t%d\t%d\n", CNodesV[i].Val1(), CNodesV[i].Val2(), CEdgesV[i].Val2());
145  //}
146  }
147  if (! OutFNm.Empty()) { fclose(F); }
148 }
149 
150 } // namespace TSnap
151 
152 //#//////////////////////////////////////////////
154 template <class TVal>
155 class TSnapQueue {
156 private:
157  TInt MxFirst; // how often we move the queue to the start of the array
160 public:
161  TSnapQueue() : MxFirst(1024), First(0), Last(0), ValV(MxFirst, 0) { }
163  TSnapQueue(const int& MxVals) : MxFirst(1024+MxVals/10), First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
164  TSnapQueue(const int& MxVals, const int& MaxFirst) : MxFirst(MaxFirst),
165  First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
166  TSnapQueue(const TSnapQueue& Queue) : MxFirst(Queue.MxFirst), First(Queue.First), Last(Queue.Last), ValV(Queue.ValV) { }
168  explicit TSnapQueue(TSIn& SIn): MxFirst(SIn), First(SIn), Last(SIn), ValV(SIn) { }
170  void Save(TSOut& SOut) const { MxFirst.Save(SOut); First.Save(SOut); Last.Save(SOut); ValV.Save(SOut); }
171 
172  TSnapQueue& operator=(const TSnapQueue& Queue) { if (this != &Queue) { MxFirst=Queue.MxFirst;
173  First=Queue.First; Last=Queue.Last; ValV=Queue.ValV; } return *this; }
175  const TVal& operator[](const int& ValN) const { return ValV[First+ValN]; }
176 
178  void Clr(const bool& DoDel=true) { ValV.Clr(DoDel); First=Last=0; }
179  void Gen(const int& MxVals, const int& MaxFirst=1024) {
180  MxFirst=MaxFirst; First=Last=0; ValV.Gen(MxVals, 0); }
181 
183  bool Empty() const {return First==Last;}
185  int Len() const {return Last-First;}
187  int GetFirst() const { return First; }
189  int GetLast() const { return Last; }
190  int Reserved() const { return ValV.Reserved(); }
191 
193  const TVal& Top() const { return ValV[First]; }
195  void Pop() { First++;
196  if (First==Last) { ValV.Clr(false); First=Last=0; } }
198  void Push(const TVal& Val) {
199  if (First>0 && (First > MxFirst || ValV.Len() == ValV.Reserved()) && ! ValV.Empty()) {
200  //printf("[move cc queue.Len:%d-->%d]", ValV.Len(),Len()); TExeTm Tm;
201  memmove(ValV.BegI(), ValV.GetI(First), sizeof(TVal)*Len());
202  ValV.Del(Len(), ValV.Len()-1); Last-=First; First=0;
203  //printf("[%s]\n", Tm.GetStr()); fflush(stdout);
204  }
205  //if (ValV.Len() == ValV.Reserved()){ printf("[resizeCCQ]"); fflush(stdout); }
206  Last++; ValV.Add(Val);
207  }
208 };
209 
210 //#//////////////////////////////////////////////
212 
214 class TUnionFind {
215 private:
216  THash<TInt, TIntPr> KIdSetH; // key id to (parent, rank)
217 public:
219  TInt& Parent(const int& Key) { return KIdSetH.GetDat(Key).Val1; }
221  TInt& Rank(const int& Key) { return KIdSetH.GetDat(Key).Val2; }
222 public:
223  TUnionFind() : KIdSetH() { }
225  TUnionFind(const int& ExpectKeys) : KIdSetH(ExpectKeys, true) { }
226  TUnionFind(const TUnionFind& UnionFind) : KIdSetH(UnionFind.KIdSetH) { }
227  TUnionFind& operator = (const TUnionFind& UF) { KIdSetH=UF.KIdSetH; return *this; }
228 
230  int Len() const { return KIdSetH.Len(); }
232  bool IsKey(const int& Key) const { return KIdSetH.IsKey(Key); }
234  int GetKeyI(const int& KeyN) const { return KIdSetH.GetKey(KeyN); }
236  int Find(const int& Key);
238  int Add(const int& Key) { KIdSetH.AddDat(Key, TIntPr(-1, 0)); return Key; }
240  void Union(const int& Key1, const int& Key2);
242  bool IsSameSet(const int& Key1, const int& Key2) {
243  return Find(Key1) == Find(Key2); }
245  void Dump();
246 };
247 
248 //#//////////////////////////////////////////////
250 
252 template <class TVal, class TCmp = TLss<TVal> >
253 class THeap {
254 private:
257 private:
258  void PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val);
259  void AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val);
260  void MakeHeap(const int& First, const int& Len);
261 public:
262  THeap() : HeapV() { }
263  THeap(const int& MxVals) : Cmp(), HeapV(MxVals, 0) { }
264  THeap(const TCmp& _Cmp) : Cmp(_Cmp), HeapV() { }
265  THeap(const TVec<TVal>& Vec) : Cmp(), HeapV(Vec) { MakeHeap(); }
266  THeap(const TVec<TVal>& Vec, const TCmp& _Cmp) : Cmp(_Cmp), HeapV(Vec) { MakeHeap(); }
267  THeap(const THeap& Heap) : Cmp(Heap.Cmp), HeapV(Heap.HeapV) { }
268  THeap& operator = (const THeap& H) { Cmp=H.Cmp; HeapV=H.HeapV; return *this; }
269 
271  const TVal& TopHeap() const { return HeapV[0]; }
273  void PushHeap(const TVal& Val);
275  TVal PopHeap();
277  int Len() const { return HeapV.Len(); }
279  bool Empty() const { return HeapV.Empty(); }
281  const TVec<TVal>& operator()() const { return HeapV; }
283  TVec<TVal>& operator()() { return HeapV; }
285  void Add(const TVal& Val) { HeapV.Add(Val); }
287  void MakeHeap() { MakeHeap(0, Len()); }
288 };
289 
290 template <class TVal, class TCmp>
291 void THeap<TVal, TCmp>::PushHeap(const TVal& Val) {
292  HeapV.Add(Val);
293  PushHeap(0, HeapV.Len()-1, 0, Val);
294 }
295 
296 template <class TVal, class TCmp>
298  IAssert(! HeapV.Empty());
299  const TVal Top = HeapV[0];
300  HeapV[0] = HeapV.Last();
301  HeapV.DelLast();
302  if (! HeapV.Empty()) {
303  AdjustHeap(0, 0, HeapV.Len(), HeapV[0]);
304  }
305  return Top;
306 }
307 
308 template <class TVal, class TCmp>
309 void THeap<TVal, TCmp>::PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val) {
310  int Parent = (HoleIdx-1)/2;
311  while (HoleIdx > Top && Cmp(HeapV[First+Parent], Val)) {
312  HeapV[First+HoleIdx] = HeapV[First+Parent];
313  HoleIdx = Parent; Parent = (HoleIdx-1)/2;
314  }
315  HeapV[First+HoleIdx] = Val;
316 }
317 
318 template <class TVal, class TCmp>
319 void THeap<TVal, TCmp>::AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val) {
320  const int Top = HoleIdx;
321  int Right = 2*HoleIdx+2;
322  while (Right < Len) {
323  if (Cmp(HeapV[First+Right], HeapV[First+Right-1])) { Right--; }
324  HeapV[First+HoleIdx] = HeapV[First+Right];
325  HoleIdx = Right; Right = 2*(Right+1); }
326  if (Right == Len) {
327  HeapV[First+HoleIdx] = HeapV[First+Right-1];
328  HoleIdx = Right-1; }
329  PushHeap(First, HoleIdx, Top, Val);
330 }
331 
332 template <class TVal, class TCmp>
333 void THeap<TVal, TCmp>::MakeHeap(const int& First, const int& Len) {
334  if (Len < 2) { return; }
335  int Parent = (Len-2)/2;
336  while (true) {
337  AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
338  if (Parent == 0) { return; }
339  Parent--;
340  }
341 }
342 
int GetLast() const
Returns the location of the last element in the queue.
Definition: gbase.h:189
THeap(const THeap &Heap)
Definition: gbase.h:267
#define IAssert(Cond)
Definition: bd.h:262
TVec< TVal > HeapV
Definition: gbase.h:256
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:29
int64 GetTriads(const PGraph &Graph, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:194
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:537
void MakeHeap()
Builds a heap from a set of elements.
Definition: gbase.h:287
TVec< TVal > ValV
Definition: gbase.h:159
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:238
TCmp Cmp
Definition: gbase.h:255
TSnapQueue(TSIn &SIn)
Constructor that loads the queue from a (binary) stream SIn.
Definition: gbase.h:168
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:279
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:285
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
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:278
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:271
TInt First
Definition: gbase.h:158
void Save(TSOut &SOut) const
Definition: dt.h:1057
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:1089
TSnapQueue & operator=(const TSnapQueue &Queue)
Definition: gbase.h:172
Tests (at compile time) if the graph is directed.
Definition: gbase.h:25
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:175
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
default value, no flags
Definition: gbase.h:12
TInt Last
Definition: gbase.h:158
TUnionFind & operator=(const TUnionFind &UF)
Definition: gbase.h:227
void Gen(const int &MxVals, const int &MaxFirst=1024)
Definition: gbase.h:179
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:885
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
void Pop()
Removes the first element from the queue.
Definition: gbase.h:195
TStr GetFlagStr(const TGraphFlag &GraphFlag)
Returns a string representation of a flag.
Definition: gbase.cpp:5
THeap(const int &MxVals)
Definition: gbase.h:263
THeap()
Definition: gbase.h:262
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:183
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:216
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
bool IsKey(const int &Key) const
Returns true if the structure contains element Key.
Definition: gbase.h:232
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:1087
THeap(const TCmp &_Cmp)
Definition: gbase.h:264
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:38
Tests (at compile time) if the graph is a network with data on edges.
Definition: gbase.h:31
int GetKeyI(const int &KeyN) const
Returns the element KeyN.
Definition: gbase.h:234
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:253
Definition: bd.h:402
THeap(const TVec< TVal > &Vec, const TCmp &_Cmp)
Definition: gbase.h:266
Tests (at compile time) if the graph is a multigraph with multiple edges between the same nodes...
Definition: gbase.h:27
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:157
TUnionFind(const TUnionFind &UnionFind)
Definition: gbase.h:226
const TVec< TVal > & operator()() const
Returns a reference to the vector containing the elements of the heap.
Definition: gbase.h:281
int Len() const
Returns the number of elements in the structure.
Definition: gbase.h:230
int Len() const
Returns the number of elements in the queue.
Definition: gbase.h:185
Definition: fl.h:128
TInt & Rank(const int &Key)
Returns the rank of element Key.
Definition: gbase.h:221
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:178
Definition: dt.h:1041
int GetFirst() const
Returns the location of the first element in the queue.
Definition: gbase.h:187
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:163
TSnapQueue()
Definition: gbase.h:161
int AddKey(const TKey &Key)
Definition: hash.h:327
void Dump()
Prints out the structure to standard output.
Definition: gbase.cpp:53
TStr GetStr() const
Definition: dt.h:1266
int Reserved() const
Definition: gbase.h:190
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:309
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:550
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:198
THeap & operator=(const THeap &H)
Definition: gbase.h:268
Definition: hash.h:88
TUnionFind()
Definition: gbase.h:223
Fast Queue used by the TBreathFS (uses memcpy to move objects TVal around).
Definition: gbase.h:155
TInt & Parent(const int &Key)
Returns the parent of element Key.
Definition: gbase.h:219
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:242
TVal2 Val2
Definition: ds.h:35
TUnionFind(const int &ExpectKeys)
Constructor that reserves enough memory for ExpectKeys elements.
Definition: gbase.h:225
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:193
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVal PopHeap()
Removes the top element from the heap.
Definition: gbase.h:297
Tests (at compile time) if the nodes store only out-edges, but not in-edges.
Definition: gbase.h:33
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:319
network with data on nodes
Definition: gbase.h:15
int Len() const
Returns the number of elements in the heap.
Definition: gbase.h:277
char * CStr()
Definition: dt.h:476
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
int Len() const
Definition: hash.h:186
TIter GetI(const TSizeTy &ValN) const
Returns an iterator an element at position ValN.
Definition: ds.h:554
TGraphFlag_
Graph Flags, used for quick testing of graph types.
Definition: gbase.h:11
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
Tests (at compile time) if the graph is a bipartite graph type.
Definition: gbase.h:35
TSnapQueue(const TSnapQueue &Queue)
Definition: gbase.h:166
Union Find class (Disjoint-set data structure).
Definition: gbase.h:214
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
TVec< TVal > & operator()()
Returns a reference to the vector containing the elements of the heap.
Definition: gbase.h:283
bipartite graph
Definition: gbase.h:18
TSnapQueue(const int &MxVals, const int &MaxFirst)
Definition: gbase.h:164
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
void Save(TSOut &SOut) const
Saves the queue to a (binary) stream SOut.
Definition: gbase.h:170
THeap(const TVec< TVal > &Vec)
Definition: gbase.h:265
void PrintInfo(const PGraph &Graph, const TStr &Desc="", const TStr &OutFNm="", const bool &Fast=true)
Prints basic graph statistics.
Definition: gbase.h:84