SNAP Library 2.3, Developer 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
bfsdfs.h
Go to the documentation of this file.
1 namespace TSnap {
2 
4 // BFS and DFS
6 
9 template <class PGraph> PNGraph GetBfsTree(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn);
11 template <class PGraph> int GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, int& TreeSzX, int& TreeDepthX);
13 
15 template <class PGraph> int GetNodesAtHop(const PGraph& Graph, const int& StartNId, const int& Hop, TIntV& NIdV, const bool& IsDir=false);
17 
19 template <class PGraph> int GetNodesAtHops(const PGraph& Graph, const int& StartNId, TIntPrV& HopCntV, const bool& IsDir=false);
20 
22 // Shortest paths
24 
26 template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir=false);
28 
32 template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir=false, const int& MaxDist=TInt::Mx);
33 
35 // Diameter
36 
38 
40 template <class PGraph> int GetBfsFullDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir=false);
42 
44 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir=false);
46 
48 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiamX, int& FullDiamX);
50 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiamX, int& FullDiamX, double& AvgSPLX);
52 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const TIntV& SubGraphNIdV, const bool& IsDir, double& EffDiamX, int& FullDiamX);
53 
54 // TODO: Implement in the future
55 //template <class PGraph> int GetRangeDist(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir=false);
56 //template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir=false, const int& MaxDist=1000);
57 //template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, const TIntSet& TargetSet, const bool& IsDir, TIntV& PathNIdV);
58 //template <class PGraph> int GetShortPath(TIntH& NIdPrnH, TCcQueue<int>& NIdQ, const PGraph& Graph, const int& SrcNId, const TIntSet& TargetSet, const bool& IsDir, TIntV& PathNIdV);
59 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir=false);
60 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, int& MxDistNId);
61 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, int& MxDistNId, TCcQueue<int>& NIdQ, TCcQueue<int>& DistQ, TIntSet& VisitedH);
62 //template <class PGraph> int GetMxGreedyDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir=false);
63 //template <class PGraph> int GetMxGreedyDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, TCcQueue<int>& NIdQ, TCcQueue<int>& DistQ, TIntSet& VisitedH);
64 //template <class PGraph> PNGraph GetShortPathsSubGraph(const PGraph& Graph, const TIntV& SubGraphNIdV);
65 //template <class PGraph> PGraph GetWccPathsSubGraph(const PGraph& Graph, const TIntV& NIdV);
66 //template <class PGraph> void GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOutEdges, int& TreeSz, int& TreeDepth);
67 
68 } // namespace TSnap
69 
70 //#//////////////////////////////////////////////
73 template<class PGraph>
74 class TBreathFS {
75 public:
76  PGraph Graph;
77  TSnapQueue<int> Queue;
78  TInt StartNId;
79  TIntH NIdDistH;
80 public:
81  TBreathFS(const PGraph& GraphPt, const bool& InitBigQ=true) :
82  Graph(GraphPt), Queue(InitBigQ?Graph->GetNodes():1024), NIdDistH(InitBigQ?Graph->GetNodes():1024) { }
84  void SetGraph(const PGraph& GraphPt);
86  int DoBfs(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId=-1, const int& MxDist=TInt::Mx);
88  int GetNVisited() const { return NIdDistH.Len(); }
90  void GetVisitedNIdV(TIntV& NIdV) const { NIdDistH.GetKeyV(NIdV); }
93  int GetHops(const int& SrcNId, const int& DstNId) const;
96  int GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const;
97 };
98 
99 template<class PGraph>
100 void TBreathFS<PGraph>::SetGraph(const PGraph& GraphPt) {
101  Graph=GraphPt;
102  const int N=GraphPt->GetNodes();
103  if (Queue.Reserved() < N) { Queue.Gen(N); }
104  if (NIdDistH.GetReservedKeyIds() < N) { NIdDistH.Gen(N); }
105 }
106 
107 template<class PGraph>
108 int TBreathFS<PGraph>::DoBfs(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId, const int& MxDist) {
109  StartNId = StartNode;
110  IAssert(Graph->IsNode(StartNId));
111 // const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
112 // IAssertR(StartNodeI.GetOutDeg() > 0, TStr::Fmt("No neighbors from start node %d.", StartNode));
113  NIdDistH.Clr(false); NIdDistH.AddDat(StartNId, 0);
114  Queue.Clr(false); Queue.Push(StartNId);
115  int v, MaxDist = 0;
116  while (! Queue.Empty()) {
117  const int NId = Queue.Top(); Queue.Pop();
118  const int Dist = NIdDistH.GetDat(NId);
119  if (Dist == MxDist) { break; } // max distance limit reached
120  const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
121  if (FollowOut) { // out-links
122  for (v = 0; v < NodeI.GetOutDeg(); v++) { // out-links
123  const int DstNId = NodeI.GetOutNId(v);
124  if (! NIdDistH.IsKey(DstNId)) {
125  NIdDistH.AddDat(DstNId, Dist+1);
126  MaxDist = TMath::Mx(MaxDist, Dist+1);
127  if (DstNId == TargetNId) { return MaxDist; }
128  Queue.Push(DstNId);
129  }
130  }
131  }
132  if (FollowIn) { // in-links
133  for (v = 0; v < NodeI.GetInDeg(); v++) {
134  const int DstNId = NodeI.GetInNId(v);
135  if (! NIdDistH.IsKey(DstNId)) {
136  NIdDistH.AddDat(DstNId, Dist+1);
137  MaxDist = TMath::Mx(MaxDist, Dist+1);
138  if (DstNId == TargetNId) { return MaxDist; }
139  Queue.Push(DstNId);
140  }
141  }
142  }
143  }
144  return MaxDist;
145 }
146 
147 template<class PGraph>
148 int TBreathFS<PGraph>::GetHops(const int& SrcNId, const int& DstNId) const {
149  TInt Dist;
150  if (SrcNId!=StartNId) { return -1; }
151  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
152  return Dist.Val;
153 }
154 
155 template<class PGraph>
156 int TBreathFS<PGraph>::GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const {
157  PathNIdV.Clr(false);
158  if (SrcNId!=StartNId || ! NIdDistH.IsKey(DstNId)) { return -1; }
159  PathNIdV.Add(DstNId);
160  TIntV CloserNIdV;
161  int CurNId = DstNId;
162  TInt CurDist, NextDist;
163  while (CurNId != SrcNId) {
164  typename PGraph::TObj::TNodeI NI = Graph->GetNI(CurNId);
165  IAssert(NIdDistH.IsKeyGetDat(CurNId, CurDist));
166  CloserNIdV.Clr(false);
167  for (int e = 0; e < NI.GetDeg(); e++) {
168  const int Next = NI.GetNbrNId(e);
169  if (NIdDistH.IsKeyGetDat(Next, NextDist)) {
170  if (NextDist == CurDist-1) { CloserNIdV.Add(Next); }
171  }
172  }
173  IAssert(! CloserNIdV.Empty());
174  CurNId = CloserNIdV[TInt::Rnd.GetUniDevInt(CloserNIdV.Len())];
175  PathNIdV.Add(CurNId);
176  }
177  PathNIdV.Reverse();
178  return PathNIdV.Len()-1;
179 }
180 
182 // Implementation
183 namespace TSnap {
184 
185 template <class PGraph>
186 PNGraph GetBfsTree(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn) {
187  TBreathFS<PGraph> BFS(Graph, false);
188  BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
189  PNGraph Tree = TNGraph::New();
190  BFS.NIdDistH.SortByDat();
191  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
192  const int NId = BFS.NIdDistH.GetKey(i);
193  const int Dist = BFS.NIdDistH[i];
194  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
195  if (!Tree->IsNode(NId)) {
196  Tree->AddNode(NId);
197  }
198  if (FollowOut) {
199  for (int e = 0; e < NI.GetInDeg(); e++) {
200  const int Prev = NI.GetInNId(e);
201  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
202  Tree->AddEdge(Prev, NId); }
203  }
204  }
205  if (FollowIn) {
206  for (int e = 0; e < NI.GetOutDeg(); e++) {
207  const int Prev = NI.GetOutNId(e);
208  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
209  Tree->AddEdge(Prev, NId); }
210  }
211  }
212  }
213  return Tree;
214 }
215 
216 template <class PGraph>
217 int GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, int& TreeSz, int& TreeDepth) {
218  TBreathFS<PGraph> BFS(Graph);
219  BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
220  TreeSz = BFS.NIdDistH.Len();
221  TreeDepth = 0;
222  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
223  TreeDepth = TMath::Mx(TreeDepth, BFS.NIdDistH[i].Val);
224  }
225  return TreeSz;
226 }
227 
228 template <class PGraph>
229 int GetNodesAtHop(const PGraph& Graph, const int& StartNId, const int& Hop, TIntV& NIdV, const bool& IsDir) {
230  TBreathFS<PGraph> BFS(Graph);
231  BFS.DoBfs(StartNId, true, !IsDir, -1, Hop);
232  NIdV.Clr(false);
233  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
234  if (BFS.NIdDistH[i] == Hop) {
235  NIdV.Add(BFS.NIdDistH.GetKey(i)); }
236  }
237  return NIdV.Len();
238 }
239 
240 template <class PGraph>
241 int GetNodesAtHops(const PGraph& Graph, const int& StartNId, TIntPrV& HopCntV, const bool& IsDir) {
242  TBreathFS<PGraph> BFS(Graph);
243  BFS.DoBfs(StartNId, true, !IsDir, -1, TInt::Mx);
244  TIntH HopCntH;
245  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
246  HopCntH.AddDat(BFS.NIdDistH[i]) += 1;
247  }
248  HopCntH.GetKeyDatPrV(HopCntV);
249  HopCntV.Sort();
250  return HopCntV.Len();
251 }
252 
253 template <class PGraph>
254 int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir, const int& MaxDist) {
255  TBreathFS<PGraph> BFS(Graph);
256  BFS.DoBfs(SrcNId, true, ! IsDir, -1, MaxDist);
257  NIdToDistH.Clr();
258  NIdToDistH.Swap(BFS.NIdDistH);
259  return NIdToDistH[NIdToDistH.Len()-1];
260 }
261 
262 template <class PGraph>
263 int GetShortPath(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir) {
264  TBreathFS<PGraph> BFS(Graph);
265  BFS.DoBfs(SrcNId, true, ! IsDir, DstNId, TInt::Mx);
266  return BFS.GetHops(SrcNId, DstNId);
267 }
268 
269 template <class PGraph>
270 int GetBfsFullDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
271  int FullDiam;
272  double EffDiam;
273  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
274  return FullDiam;
275 }
276 
277 template <class PGraph>
278 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
279  int FullDiam;
280  double EffDiam;
281  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
282  return EffDiam;
283 }
284 
285 template <class PGraph>
286 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam) {
287  double AvgDiam;
288  EffDiam = -1; FullDiam = -1;
289  return GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam, AvgDiam);
290 }
291 
292 template <class PGraph>
293 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam, double& AvgSPL) {
294  EffDiam = -1; FullDiam = -1; AvgSPL = -1;
295  TIntFltH DistToCntH;
296  TBreathFS<PGraph> BFS(Graph);
297  // shotest paths
298  TIntV NodeIdV;
299  Graph->GetNIdV(NodeIdV); NodeIdV.Shuffle(TInt::Rnd);
300  for (int tries = 0; tries < TMath::Mn(NTestNodes, Graph->GetNodes()); tries++) {
301  const int NId = NodeIdV[tries];
302  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
303  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
304  DistToCntH.AddDat(BFS.NIdDistH[i]) += 1; }
305  }
306  TIntFltKdV DistNbrsPdfV;
307  double SumPathL=0, PathCnt=0;
308  for (int i = 0; i < DistToCntH.Len(); i++) {
309  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
310  SumPathL += DistToCntH.GetKey(i) * DistToCntH[i];
311  PathCnt += DistToCntH[i];
312  }
313  DistNbrsPdfV.Sort();
314  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
315  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
316  AvgSPL = SumPathL/PathCnt; // average shortest path length
317  return EffDiam;
318 }
319 
320 template <class PGraph>
321 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const TIntV& SubGraphNIdV, const bool& IsDir, double& EffDiam, int& FullDiam) {
322  EffDiam = -1;
323  FullDiam = -1;
324 
325  TIntFltH DistToCntH;
326  TBreathFS<PGraph> BFS(Graph);
327  // shotest paths
328  TIntV NodeIdV(SubGraphNIdV); NodeIdV.Shuffle(TInt::Rnd);
329  TInt Dist;
330  for (int tries = 0; tries < TMath::Mn(NTestNodes, SubGraphNIdV.Len()); tries++) {
331  const int NId = NodeIdV[tries];
332  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
333  for (int i = 0; i < SubGraphNIdV.Len(); i++) {
334  if (BFS.NIdDistH.IsKeyGetDat(SubGraphNIdV[i], Dist)) {
335  DistToCntH.AddDat(Dist) += 1;
336  }
337  }
338  }
339  TIntFltKdV DistNbrsPdfV;
340  for (int i = 0; i < DistToCntH.Len(); i++) {
341  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
342  }
343  DistNbrsPdfV.Sort();
344  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
345  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
346  return EffDiam; // average shortest path length
347 }
348 
349 } // namespace TSnap
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TBreathFS::GetHops
int GetHops(const int &SrcNId, const int &DstNId) const
Definition: bfsdfs.h:148
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:78
TSnap::GetBfsFullDiam
int GetBfsFullDiam(const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
Returns the (approximation of the) Diameter (maximum shortest path length) of a graph (by performing ...
Definition: bfsdfs.h:270
TSnap::GetBfsEffDiam
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
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1043
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:405
TInt::Mx
static const int Mx
Definition: dt.h:1046
TBreathFS::DoBfs
int DoBfs(const int &StartNode, const bool &FollowOut, const bool &FollowIn, const int &TargetNId=-1, const int &MxDist=TInt::Mx)
Performs BFS from node id StartNode for at maps MxDist steps by only following in-links (parameter Fo...
Definition: bfsdfs.h:108
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TIntFltKd
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:371
TBreathFS::TBreathFS
TBreathFS(const PGraph &GraphPt, const bool &InitBigQ=true)
Definition: bfsdfs.h:81
TSnap::GetNodesAtHops
int GetNodesAtHops(const PGraph &Graph, const int &StartNId, TIntPrV &HopCntV, const bool &IsDir=false)
Returns the number of nodes at each hop distance from the starting node StartNId. ...
Definition: bfsdfs.h:241
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:208
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1050
TBreathFS::SetGraph
void SetGraph(const PGraph &GraphPt)
Sets the graph to be used by the BFS to GraphPt and resets the data structures.
Definition: bfsdfs.h:100
TSnap::GetBfsTree
PNGraph GetBfsTree(const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn)
Returns a directed Breadth-First-Search tree rooted at StartNId.
Definition: bfsdfs.h:186
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:77
TBreathFS::GetRndPath
int GetRndPath(const int &SrcNId, const int &DstNId, TIntV &PathNIdV) const
Definition: bfsdfs.h:156
THash::Swap
void Swap(THash &Hash)
Definition: hash.h:498
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
TSnap::GetNodesAtHop
int GetNodesAtHop(const PGraph &Graph, const int &StartNId, const int &Hop, TIntV &NIdV, const bool &IsDir=false)
Finds IDs of all nodes that are at distance Hop from node StartNId.
Definition: bfsdfs.h:229
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1218
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graph.cpp:286
TSnap::TSnapDetail::CalcEffDiamPdf
double CalcEffDiamPdf(const TIntFltKdV &DistNbrsPdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) probability distribution functio...
Definition: anf.cpp:29
TNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:455
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:228
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:539
TSnap::GetSubTreeSz
int GetSubTreeSz(const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, int &TreeSzX, int &TreeDepthX)
Returns the BFS tree size (number of nodes) and depth (number of levels) by following in-links (param...
Definition: bfsdfs.h:217
TInt
Definition: dt.h:1041
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:438
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
TVec::Shuffle
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1235
TBreathFS::GetNVisited
int GetNVisited() const
Returns the number of nodes visited/reached by the BFS.
Definition: bfsdfs.h:88
THash::GetKeyDatPrV
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:454
TBreathFS::GetVisitedNIdV
void GetVisitedNIdV(TIntV &NIdV) const
Returns the IDs of the nodes visited/reached by the BFS.
Definition: bfsdfs.h:90
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:315
TPt
Definition: bd.h:196
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1250
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
TSnap::GetShortPath
int GetShortPath(const PGraph &Graph, const int &SrcNId, const int &DstNId, const bool &IsDir=false)
Returns the length of the shortest path from node SrcNId to node DstNId.
Definition: bfsdfs.h:263
THash::Len
int Len() const
Definition: hash.h:186
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
THash::SortByDat
void SortByDat(const bool &Asc=true)
Definition: hash.h:246