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.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 
180  // Randomly samples num elements from Queue and adds them to the front.
181  void Sample(const int num, TRnd& Rnd=TInt::Rnd) {
182  const int size = Last - First;
183  int loc;
184  TVal temp;
185  for (int i = 0; i < num && i < size; ++i) {
186  loc = Rnd.GetUniDevInt(size - i) + First + i;
187  temp = ValV[loc];
188  ValV[loc] = ValV[First + i];
189  ValV[First + i] = temp;
190  }
191  }
192 
194  void Clr(const bool& DoDel=true) { ValV.Clr(DoDel); First=Last=0; }
195  void Gen(const int& MxVals, const int& MaxFirst=1024) {
196  MxFirst=MaxFirst; First=Last=0; ValV.Gen(MxVals, 0); }
197 
199  bool Empty() const {return First==Last;}
201  int Len() const {return Last-First;}
203  int GetFirst() const { return First; }
205  int GetLast() const { return Last; }
206  int Reserved() const { return ValV.Reserved(); }
207 
209  const TVal& Top() const { return ValV[First]; }
211  void Pop() { First++;
212  if (First==Last) { ValV.Clr(false); First=Last=0; } }
214  void Push(const TVal& Val) {
215  if (First>0 && (First > MxFirst || ValV.Len() == ValV.Reserved()) && ! ValV.Empty()) {
216  //printf("[move cc queue.Len:%d-->%d]", ValV.Len(),Len()); TExeTm Tm;
217  memmove(ValV.BegI(), ValV.GetI(First), sizeof(TVal)*Len());
218  ValV.Del(Len(), ValV.Len()-1); Last-=First; First=0;
219  //printf("[%s]\n", Tm.GetStr()); fflush(stdout);
220  }
221  //if (ValV.Len() == ValV.Reserved()){ printf("[resizeCCQ]"); fflush(stdout); }
222  Last++; ValV.Add(Val);
223  }
224 };
225 
226 //#//////////////////////////////////////////////
228 
230 class TUnionFind {
231 private:
232  THash<TInt, TIntPr> KIdSetH; // key id to (parent, rank)
233 public:
235  TInt& Parent(const int& Key) { return KIdSetH.GetDat(Key).Val1; }
237  TInt& Rank(const int& Key) { return KIdSetH.GetDat(Key).Val2; }
238 public:
239  TUnionFind() : KIdSetH() { }
241  TUnionFind(const int& ExpectKeys) : KIdSetH(ExpectKeys, true) { }
242  TUnionFind(const TUnionFind& UnionFind) : KIdSetH(UnionFind.KIdSetH) { }
243  TUnionFind& operator = (const TUnionFind& UF) { KIdSetH=UF.KIdSetH; return *this; }
244 
246  int Len() const { return KIdSetH.Len(); }
248  bool IsKey(const int& Key) const { return KIdSetH.IsKey(Key); }
250  int GetKeyI(const int& KeyN) const { return KIdSetH.GetKey(KeyN); }
252  int Find(const int& Key);
254  int Add(const int& Key) { KIdSetH.AddDat(Key, TIntPr(-1, 0)); return Key; }
256  void Union(const int& Key1, const int& Key2);
258  bool IsSameSet(const int& Key1, const int& Key2) {
259  return Find(Key1) == Find(Key2); }
261  void Dump();
262 };
263 
264 //#//////////////////////////////////////////////
266 
268 template <class TVal, class TCmp = TLss<TVal> >
269 class THeap {
270 private:
273 private:
274  void PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val);
275  void AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val);
276  void MakeHeap(const int& First, const int& Len);
277 public:
278  THeap() : HeapV() { }
279  THeap(const int& MxVals) : Cmp(), HeapV(MxVals, 0) { }
280  THeap(const TCmp& _Cmp) : Cmp(_Cmp), HeapV() { }
281  THeap(const TVec<TVal>& Vec) : Cmp(), HeapV(Vec) { MakeHeap(); }
282  THeap(const TVec<TVal>& Vec, const TCmp& _Cmp) : Cmp(_Cmp), HeapV(Vec) { MakeHeap(); }
283  THeap(const THeap& Heap) : Cmp(Heap.Cmp), HeapV(Heap.HeapV) { }
284  THeap& operator = (const THeap& H) { Cmp=H.Cmp; HeapV=H.HeapV; return *this; }
285 
287  const TVal& TopHeap() const { return HeapV[0]; }
289  void PushHeap(const TVal& Val);
291  TVal PopHeap();
293  int Len() const { return HeapV.Len(); }
295  bool Empty() const { return HeapV.Empty(); }
297  const TVec<TVal>& operator()() const { return HeapV; }
299  TVec<TVal>& operator()() { return HeapV; }
301  void Add(const TVal& Val) { HeapV.Add(Val); }
303  void MakeHeap() { MakeHeap(0, Len()); }
304 };
305 
306 template <class TVal, class TCmp>
307 void THeap<TVal, TCmp>::PushHeap(const TVal& Val) {
308  HeapV.Add(Val);
309  PushHeap(0, HeapV.Len()-1, 0, Val);
310 }
311 
312 template <class TVal, class TCmp>
314  IAssert(! HeapV.Empty());
315  const TVal Top = HeapV[0];
316  HeapV[0] = HeapV.Last();
317  HeapV.DelLast();
318  if (! HeapV.Empty()) {
319  AdjustHeap(0, 0, HeapV.Len(), HeapV[0]);
320  }
321  return Top;
322 }
323 
324 template <class TVal, class TCmp>
325 void THeap<TVal, TCmp>::PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val) {
326  int Parent = (HoleIdx-1)/2;
327  while (HoleIdx > Top && Cmp(HeapV[First+Parent], Val)) {
328  HeapV[First+HoleIdx] = HeapV[First+Parent];
329  HoleIdx = Parent; Parent = (HoleIdx-1)/2;
330  }
331  HeapV[First+HoleIdx] = Val;
332 }
333 
334 template <class TVal, class TCmp>
335 void THeap<TVal, TCmp>::AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val) {
336  const int Top = HoleIdx;
337  int Right = 2*HoleIdx+2;
338  while (Right < Len) {
339  if (Cmp(HeapV[First+Right], HeapV[First+Right-1])) { Right--; }
340  HeapV[First+HoleIdx] = HeapV[First+Right];
341  HoleIdx = Right; Right = 2*(Right+1); }
342  if (Right == Len) {
343  HeapV[First+HoleIdx] = HeapV[First+Right-1];
344  HoleIdx = Right-1; }
345  PushHeap(First, HoleIdx, Top, Val);
346 }
347 
348 template <class TVal, class TCmp>
349 void THeap<TVal, TCmp>::MakeHeap(const int& First, const int& Len) {
350  if (Len < 2) { return; }
351  int Parent = (Len-2)/2;
352  while (true) {
353  AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
354  if (Parent == 0) { return; }
355  Parent--;
356  }
357 }
358 
int GetLast() const
Returns the location of the last element in the queue.
Definition: gbase.h:205
THeap(const THeap &Heap)
Definition: gbase.h:283
#define IAssert(Cond)
Definition: bd.h:262
TVec< TVal > HeapV
Definition: gbase.h:272
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
Main namespace for all the Snap global entities.
Definition: alg.h:1
int64 GetTriads(const PGraph &Graph, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:246
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:303
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:254
TCmp Cmp
Definition: gbase.h:271
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:295
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:301
Definition: dt.h:11
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:424
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:287
TInt First
Definition: gbase.h:161
void Save(TSOut &SOut) const
Definition: dt.h:1153
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:1185
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:243
void Gen(const int &MxVals, const int &MaxFirst=1024)
Definition: gbase.h:195
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
static TRnd Rnd
Definition: dt.h:1146
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:211
TStr GetFlagStr(const TGraphFlag &GraphFlag)
Returns a string representation of a flag.
Definition: gbase.cpp:5
THeap(const int &MxVals)
Definition: gbase.h:279
THeap()
Definition: gbase.h:278
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:199
THash< TInt, TIntPr > KIdSetH
Definition: gbase.h:232
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:248
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:1183
THeap(const TCmp &_Cmp)
Definition: gbase.h:280
#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:250
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:269
Definition: bd.h:402
THeap(const TVec< TVal > &Vec, const TCmp &_Cmp)
Definition: gbase.h:282
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:242
const TVec< TVal > & operator()() const
Returns a reference to the vector containing the elements of the heap.
Definition: gbase.h:297
int Len() const
Returns the number of elements in the structure.
Definition: gbase.h:246
int Len() const
Returns the number of elements in the queue.
Definition: gbase.h:201
Definition: fl.h:128
TInt & Rank(const int &Key)
Returns the rank of element Key.
Definition: gbase.h:237
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:194
Definition: dt.h:1137
int GetFirst() const
Returns the location of the first element in the queue.
Definition: gbase.h:203
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:1363
void Sample(const int num, TRnd &Rnd=TInt::Rnd)
Definition: gbase.h:181
int Reserved() const
Definition: gbase.h:206
long long int64
Definition: bd.h:27
Definition: dt.h:412
bool Empty() const
Definition: dt.h:491
sentinel, last value for iteration
Definition: gbase.h:19
void PushHeap(const int &First, int HoleIdx, const int &Top, TVal Val)
Definition: gbase.h:325
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:214
THeap & operator=(const THeap &H)
Definition: gbase.h:284
TUnionFind()
Definition: gbase.h:239
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:235
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:258
TVal2 Val2
Definition: ds.h:35
TUnionFind(const int &ExpectKeys)
Constructor that reserves enough memory for ExpectKeys elements.
Definition: gbase.h:241
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:209
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:313
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:335
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:293
char * CStr()
Definition: dt.h:479
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:230
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:299
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:281
void PrintInfo(const PGraph &Graph, const TStr &Desc="", const TStr &OutFNm="", const bool &Fast=true)
Prints basic graph statistics.
Definition: gbase.h:87