SNAP Library 4.1, Developer Reference  2018-07-26 16:30:42
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 
52 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiamX, int& FullDiamX, double& AvgSPLX);
54 
57 template <class PGraph> double GetBfsEffDiamAll(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiamX, int& FullDiamX, double& AvgSPLX);
59 
61 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const TIntV& SubGraphNIdV, const bool& IsDir, double& EffDiamX, int& FullDiamX);
62 
63 // TODO: Implement in the future
64 //template <class PGraph> int GetRangeDist(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir=false);
65 //template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir=false, const int& MaxDist=1000);
66 //template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, const TIntSet& TargetSet, const bool& IsDir, TIntV& PathNIdV);
67 //template <class PGraph> int GetShortPath(TIntH& NIdPrnH, TCcQueue<int>& NIdQ, const PGraph& Graph, const int& SrcNId, const TIntSet& TargetSet, const bool& IsDir, TIntV& PathNIdV);
68 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir=false);
69 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, int& MxDistNId);
70 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, int& MxDistNId, TCcQueue<int>& NIdQ, TCcQueue<int>& DistQ, TIntSet& VisitedH);
71 //template <class PGraph> int GetMxGreedyDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir=false);
72 //template <class PGraph> int GetMxGreedyDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, TCcQueue<int>& NIdQ, TCcQueue<int>& DistQ, TIntSet& VisitedH);
73 //template <class PGraph> PNGraph GetShortPathsSubGraph(const PGraph& Graph, const TIntV& SubGraphNIdV);
74 //template <class PGraph> PGraph GetWccPathsSubGraph(const PGraph& Graph, const TIntV& NIdV);
75 //template <class PGraph> void GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOutEdges, int& TreeSz, int& TreeDepth);
76 
77 } // namespace TSnap
78 
79 //#//////////////////////////////////////////////
82 template<class PGraph>
83 class TBreathFS {
84 public:
85  PGraph Graph;
86  TSnapQueue<int> Queue;
87  TInt StartNId;
88  TIntH NIdDistH;
89 public:
90  TBreathFS(const PGraph& GraphPt, const bool& InitBigQ=true) :
91  Graph(GraphPt), Queue(InitBigQ?Graph->GetNodes():1024), NIdDistH(InitBigQ?Graph->GetNodes():1024) { }
93  void SetGraph(const PGraph& GraphPt);
95  int DoBfs(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId=-1, const int& MxDist=TInt::Mx);
97  int DoBfsHybrid(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId=-1, const int& MxDist=TInt::Mx);
99  int GetNVisited() const { return NIdDistH.Len(); }
101  void GetVisitedNIdV(TIntV& NIdV) const { NIdDistH.GetKeyV(NIdV); }
104  int GetHops(const int& SrcNId, const int& DstNId) const;
107  int GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const;
108 
109 /* Private variables and functions for DoBfsHybrid */
110 private:
111  int Stage; // 0, 2: top down, 1: bottom up
112  static const unsigned int alpha = 100;
113  static const unsigned int beta = 20;
114  /* Private functions */
115  bool TopDownStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn);
116  bool BottomUpStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn);
117 };
118 
119 template<class PGraph>
120 void TBreathFS<PGraph>::SetGraph(const PGraph& GraphPt) {
121  Graph=GraphPt;
122  const int N=GraphPt->GetNodes();
123  if (Queue.Reserved() < N) { Queue.Gen(N); }
124  if (NIdDistH.GetReservedKeyIds() < N) { NIdDistH.Gen(N); }
125 }
126 
127 template<class PGraph>
128 int TBreathFS<PGraph>::DoBfs(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId, const int& MxDist) {
129  StartNId = StartNode;
130  IAssert(Graph->IsNode(StartNId));
131 // const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
132 // IAssertR(StartNodeI.GetOutDeg() > 0, TStr::Fmt("No neighbors from start node %d.", StartNode));
133  NIdDistH.Clr(false); NIdDistH.AddDat(StartNId, 0);
134  Queue.Clr(false); Queue.Push(StartNId);
135  int v, MaxDist = 0;
136  while (! Queue.Empty()) {
137  const int NId = Queue.Top(); Queue.Pop();
138  const int Dist = NIdDistH.GetDat(NId);
139  if (Dist == MxDist) { break; } // max distance limit reached
140  const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
141  if (FollowOut) { // out-links
142  for (v = 0; v < NodeI.GetOutDeg(); v++) { // out-links
143  const int DstNId = NodeI.GetOutNId(v);
144  if (! NIdDistH.IsKey(DstNId)) {
145  NIdDistH.AddDat(DstNId, Dist+1);
146  MaxDist = TMath::Mx(MaxDist, Dist+1);
147  if (DstNId == TargetNId) { return MaxDist; }
148  Queue.Push(DstNId);
149  }
150  }
151  }
152  if (FollowIn) { // in-links
153  for (v = 0; v < NodeI.GetInDeg(); v++) {
154  const int DstNId = NodeI.GetInNId(v);
155  if (! NIdDistH.IsKey(DstNId)) {
156  NIdDistH.AddDat(DstNId, Dist+1);
157  MaxDist = TMath::Mx(MaxDist, Dist+1);
158  if (DstNId == TargetNId) { return MaxDist; }
159  Queue.Push(DstNId);
160  }
161  }
162  }
163  }
164  return MaxDist;
165 }
166 
167 template<class PGraph>
168 int TBreathFS<PGraph>::DoBfsHybrid(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId, const int& MxDist) {
169  StartNId = StartNode;
170  IAssert(Graph->IsNode(StartNId));
171  if (TargetNId == StartNode) return 0;
172  const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
173 
174  // Initialize vector
175  TIntV NIdDistV(Graph->GetMxNId() + 1);
176  for (int i = 0; i < NIdDistV.Len(); i++) {
177  NIdDistV.SetVal(i, -1);
178  }
179  TIntV *Frontier = new TIntV(Graph->GetNodes(), 0);
180  TIntV *NextFrontier = new TIntV(Graph->GetNodes(), 0);
181 
182  NIdDistV.SetVal(StartNId, 0);
183  Frontier->Add(StartNId);
184  Stage = 0;
185  int MaxDist = -1;
186  const unsigned int TotalNodes = Graph->GetNodes();
187  unsigned int UnvisitedNodes = Graph->GetNodes();
188  while (! Frontier->Empty()) {
189  MaxDist += 1;
190  NextFrontier->Clr(false);
191  if (MaxDist == MxDist) { break; } // max distance limit reached
192 
193  UnvisitedNodes -= Frontier->Len();
194  if (Stage == 0 && UnvisitedNodes / Frontier->Len() < alpha) {
195  Stage = 1;
196  } else if (Stage == 1 && TotalNodes / Frontier->Len() > beta) {
197  Stage = 2;
198  }
199 
200  // Top down or bottom up depending on stage
201  bool targetFound = false;
202  if (Stage == 0 || Stage == 2) {
203  targetFound = TopDownStep(NIdDistV, Frontier, NextFrontier, MaxDist, TargetNId, FollowOut, FollowIn);
204  } else {
205  targetFound = BottomUpStep(NIdDistV, Frontier, NextFrontier, MaxDist, TargetNId, FollowOut, FollowIn);
206  }
207  if (targetFound) {
208  MaxDist = NIdDistV[TargetNId];
209  break;
210  }
211 
212  // swap Frontier and NextFrontier
213  TIntV *temp = Frontier;
214  Frontier = NextFrontier;
215  NextFrontier = temp;
216  }
217 
218  delete Frontier;
219  delete NextFrontier;
220  // Transform vector to hash table
221  NIdDistH.Clr(false);
222  for (int NId = 0; NId < NIdDistV.Len(); NId++) {
223  if (NIdDistV[NId] != -1) {
224  NIdDistH.AddDat(NId, NIdDistV[NId]);
225  }
226  }
227  return MaxDist;
228 }
229 
230 template<class PGraph>
231 bool TBreathFS<PGraph>::TopDownStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn) {
232  for (TIntV::TIter it = Frontier->BegI(); it != Frontier->EndI(); ++it) { // loop over frontier
233  const int NId = *it;
234  const int Dist = NIdDistV[NId];
235  IAssert(Dist == MaxDist); // Must equal to MaxDist
236  const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
237  if (FollowOut) {
238  for (int v = 0; v < NodeI.GetOutDeg(); v++) {
239  const int NeighborNId = NodeI.GetOutNId(v);
240  if (NIdDistV[NeighborNId] == -1) {
241  NIdDistV.SetVal(NeighborNId, Dist+1);
242  if (NeighborNId == TargetNId) return true;
243  NextFrontier->Add(NeighborNId);
244  }
245  }
246  }
247  if (FollowIn) {
248  for (int v = 0; v < NodeI.GetInDeg(); v++) {
249  const int NeighborNId = NodeI.GetInNId(v);
250  if (NIdDistV[NeighborNId] == -1) {
251  NIdDistV.SetVal(NeighborNId, Dist+1);
252  if (NeighborNId == TargetNId) return true;
253  NextFrontier->Add(NeighborNId);
254  }
255  }
256  }
257  }
258  return false;
259 }
260 
261 template<class PGraph>
262 bool TBreathFS<PGraph>::BottomUpStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn) {
263  for (typename PGraph::TObj::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
264  const int NId = NodeI.GetId();
265  if (NIdDistV[NId] == -1) {
266  if (FollowOut) {
267  for (int v = 0; v < NodeI.GetInDeg(); v++) {
268  const int ParentNId = NodeI.GetInNId(v);
269  if (NIdDistV[ParentNId] == MaxDist) {
270  NIdDistV[NId] = MaxDist + 1;
271  if (NId == TargetNId) return true;
272  NextFrontier->Add(NId);
273  break;
274  }
275  }
276  }
277  if (FollowIn && NIdDistV[NId] == -1) {
278  for (int v = 0; v < NodeI.GetOutDeg(); v++) {
279  const int ParentNId = NodeI.GetOutNId(v);
280  if (NIdDistV[ParentNId] == MaxDist) {
281  NIdDistV[NId] = MaxDist + 1;
282  if (NId == TargetNId) return true;
283  NextFrontier->Add(NId);
284  break;
285  }
286  }
287  }
288  }
289  }
290  return false;
291 }
292 
293 template<class PGraph>
294 int TBreathFS<PGraph>::GetHops(const int& SrcNId, const int& DstNId) const {
295  TInt Dist;
296  if (SrcNId!=StartNId) { return -1; }
297  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
298  return Dist.Val;
299 }
300 
301 template<class PGraph>
302 int TBreathFS<PGraph>::GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const {
303  PathNIdV.Clr(false);
304  if (SrcNId!=StartNId || ! NIdDistH.IsKey(DstNId)) { return -1; }
305  PathNIdV.Add(DstNId);
306  TIntV CloserNIdV;
307  int CurNId = DstNId;
308  TInt CurDist, NextDist;
309  while (CurNId != SrcNId) {
310  typename PGraph::TObj::TNodeI NI = Graph->GetNI(CurNId);
311  IAssert(NIdDistH.IsKeyGetDat(CurNId, CurDist));
312  CloserNIdV.Clr(false);
313  for (int e = 0; e < NI.GetDeg(); e++) {
314  const int Next = NI.GetNbrNId(e);
315  if (NIdDistH.IsKeyGetDat(Next, NextDist)) {
316  if (NextDist == CurDist-1) { CloserNIdV.Add(Next); }
317  }
318  }
319  IAssert(! CloserNIdV.Empty());
320  CurNId = CloserNIdV[TInt::Rnd.GetUniDevInt(CloserNIdV.Len())];
321  PathNIdV.Add(CurNId);
322  }
323  PathNIdV.Reverse();
324  return PathNIdV.Len()-1;
325 }
326 
328 // Implementation
329 namespace TSnap {
330 
331 template <class PGraph>
332 PNGraph GetBfsTree(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn) {
333  TBreathFS<PGraph> BFS(Graph);
334  BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
335  PNGraph Tree = TNGraph::New();
336  BFS.NIdDistH.SortByDat();
337  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
338  const int NId = BFS.NIdDistH.GetKey(i);
339  const int Dist = BFS.NIdDistH[i];
340  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
341  if (!Tree->IsNode(NId)) {
342  Tree->AddNode(NId);
343  }
344  if (FollowOut) {
345  for (int e = 0; e < NI.GetInDeg(); e++) {
346  const int Prev = NI.GetInNId(e);
347  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
348  Tree->AddEdge(Prev, NId); }
349  }
350  }
351  if (FollowIn) {
352  for (int e = 0; e < NI.GetOutDeg(); e++) {
353  const int Prev = NI.GetOutNId(e);
354  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
355  Tree->AddEdge(Prev, NId); }
356  }
357  }
358  }
359  return Tree;
360 }
361 
362 template <class PGraph>
363 int GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, int& TreeSz, int& TreeDepth) {
364  TBreathFS<PGraph> BFS(Graph);
365  BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
366  TreeSz = BFS.NIdDistH.Len();
367  TreeDepth = 0;
368  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
369  TreeDepth = TMath::Mx(TreeDepth, BFS.NIdDistH[i].Val);
370  }
371  return TreeSz;
372 }
373 
374 template <class PGraph>
375 int GetNodesAtHop(const PGraph& Graph, const int& StartNId, const int& Hop, TIntV& NIdV, const bool& IsDir) {
376  TBreathFS<PGraph> BFS(Graph);
377  BFS.DoBfs(StartNId, true, !IsDir, -1, Hop);
378  NIdV.Clr(false);
379  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
380  if (BFS.NIdDistH[i] == Hop) {
381  NIdV.Add(BFS.NIdDistH.GetKey(i)); }
382  }
383  return NIdV.Len();
384 }
385 
386 template <class PGraph>
387 int GetNodesAtHops(const PGraph& Graph, const int& StartNId, TIntPrV& HopCntV, const bool& IsDir) {
388  TBreathFS<PGraph> BFS(Graph);
389  BFS.DoBfs(StartNId, true, !IsDir, -1, TInt::Mx);
390  TIntH HopCntH;
391  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
392  HopCntH.AddDat(BFS.NIdDistH[i]) += 1;
393  }
394  HopCntH.GetKeyDatPrV(HopCntV);
395  HopCntV.Sort();
396  return HopCntV.Len();
397 }
398 
399 template <class PGraph>
400 int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir, const int& MaxDist) {
401  TBreathFS<PGraph> BFS(Graph);
402  BFS.DoBfs(SrcNId, true, ! IsDir, -1, MaxDist);
403  NIdToDistH.Clr();
404  NIdToDistH.Swap(BFS.NIdDistH);
405  return NIdToDistH[NIdToDistH.Len()-1];
406 }
407 
408 template <class PGraph>
409 int GetShortPath(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir) {
410  TBreathFS<PGraph> BFS(Graph);
411  BFS.DoBfs(SrcNId, true, ! IsDir, DstNId, TInt::Mx);
412  return BFS.GetHops(SrcNId, DstNId);
413 }
414 
415 template <class PGraph>
416 int GetBfsFullDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
417  int FullDiam;
418  double EffDiam;
419  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
420  return FullDiam;
421 }
422 
423 template <class PGraph>
424 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
425  int FullDiam;
426  double EffDiam;
427  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
428  return EffDiam;
429 }
430 
431 template <class PGraph>
432 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam) {
433  double AvgDiam;
434  EffDiam = -1; FullDiam = -1;
435  return GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam, AvgDiam);
436 }
437 
438 template <class PGraph>
439 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam, double& AvgSPL) {
440  EffDiam = -1; FullDiam = -1; AvgSPL = -1;
441  TIntFltH DistToCntH;
442  TBreathFS<PGraph> BFS(Graph);
443  // shotest paths
444  TIntV NodeIdV;
445  Graph->GetNIdV(NodeIdV); NodeIdV.Shuffle(TInt::Rnd);
446  for (int tries = 0; tries < TMath::Mn(NTestNodes, Graph->GetNodes()); tries++) {
447  const int NId = NodeIdV[tries];
448  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
449  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
450  DistToCntH.AddDat(BFS.NIdDistH[i]) += 1; }
451  }
452  TIntFltKdV DistNbrsPdfV;
453  double SumPathL=0, PathCnt=0;
454  for (int i = 0; i < DistToCntH.Len(); i++) {
455  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
456  SumPathL += DistToCntH.GetKey(i) * DistToCntH[i];
457  PathCnt += DistToCntH[i];
458  }
459  DistNbrsPdfV.Sort();
460  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
461  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
462  AvgSPL = SumPathL/PathCnt; // average shortest path length
463  return EffDiam;
464 }
465 
466 template <class PGraph>
467 double GetBfsEffDiamAll(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam, double& AvgSPL) {
468  return GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam, AvgSPL);
469 }
470 
471 template <class PGraph>
472 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const TIntV& SubGraphNIdV, const bool& IsDir, double& EffDiam, int& FullDiam) {
473  EffDiam = -1;
474  FullDiam = -1;
475 
476  TIntFltH DistToCntH;
477  TBreathFS<PGraph> BFS(Graph);
478  // shotest paths
479  TIntV NodeIdV(SubGraphNIdV); NodeIdV.Shuffle(TInt::Rnd);
480  TInt Dist;
481  for (int tries = 0; tries < TMath::Mn(NTestNodes, SubGraphNIdV.Len()); tries++) {
482  const int NId = NodeIdV[tries];
483  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
484  for (int i = 0; i < SubGraphNIdV.Len(); i++) {
485  if (BFS.NIdDistH.IsKeyGetDat(SubGraphNIdV[i], Dist)) {
486  DistToCntH.AddDat(Dist) += 1;
487  }
488  }
489  }
490  TIntFltKdV DistNbrsPdfV;
491  for (int i = 0; i < DistToCntH.Len(); i++) {
492  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
493  }
494  DistNbrsPdfV.Sort();
495  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
496  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
497  return EffDiam; // average shortest path length
498 }
499 
500 template <class PGraph>
501 int GetShortestDistances(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, TIntV& ShortestDists) {
502  PSOut StdOut = TStdOut::New();
503  int MxNId = Graph->GetMxNId();
504  int NonNodeDepth = 2147483647; // INT_MAX
505  int InfDepth = 2147483646; // INT_MAX - 1
506  ShortestDists.Gen(MxNId);
507  for (int NId = 0; NId < MxNId; NId++) {
508  if (Graph->IsNode(NId)) { ShortestDists[NId] = InfDepth; }
509  else { ShortestDists[NId] = NonNodeDepth; }
510  }
511 
512  TIntV Vec1(MxNId, 0); // ensure enough capacity
513  TIntV Vec2(MxNId, 0); // ensure enough capacity
514 
515  ShortestDists[StartNId] = 0;
516  TIntV* PCurV = &Vec1;
517  PCurV->Add(StartNId);
518  TIntV* PNextV = &Vec2;
519  int Depth = 0; // current depth
520  while (!PCurV->Empty()) {
521  Depth++; // increase depth
522  for (int i = 0; i < PCurV->Len(); i++) {
523  int NId = PCurV->GetVal(i);
524  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
525  for (int e = 0; e < NI.GetOutDeg(); e++) {
526  const int OutNId = NI.GetOutNId(e);
527  if (ShortestDists[OutNId].Val == InfDepth) {
528  ShortestDists[OutNId] = Depth;
529  PNextV->Add(OutNId);
530  }
531  }
532  }
533  // swap pointer, no copying
534  TIntV* Tmp = PCurV;
535  PCurV = PNextV;
536  PNextV = Tmp;
537  // clear next
538  PNextV->Reduce(0); // reduce length, does not initialize new array
539  }
540  return Depth-1;
541 }
542 
543 #ifdef USE_OPENMP
544 template <class PGraph>
545 int GetShortestDistancesMP2(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, TIntV& ShortestDists) {
546  int MxNId = Graph->GetMxNId();
547  int NonNodeDepth = 2147483647; // INT_MAX
548  int InfDepth = 2147483646; // INT_MAX - 1
549  ShortestDists.Gen(MxNId);
550  #pragma omp parallel for schedule(dynamic,10000)
551  for (int NId = 0; NId < MxNId; NId++) {
552  if (Graph->IsNode(NId)) { ShortestDists[NId] = InfDepth; }
553  else { ShortestDists[NId] = NonNodeDepth; }
554  }
555 
556  TIntV Vec1(MxNId, 0); // ensure enough capacity
557  TIntV Vec2(MxNId, 0); // ensure enough capacity
558 
559  ShortestDists[StartNId] = 0;
560  TIntV* PCurV = &Vec1;
561  PCurV->Add(StartNId);
562  TIntV* PNextV = &Vec2;
563  int Depth = 0; // current depth
564 
565  while (!PCurV->Empty()) {
566  Depth++; // increase depth
567  #pragma omp parallel for schedule(dynamic,10000)
568  for (int i = 0; i < PCurV->Len(); i++) {
569  int NId = PCurV->GetVal(i);
570  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
571  for (int e = 0; e < NI.GetOutDeg(); e++) {
572  const int OutNId = NI.GetOutNId(e);
573  if (__sync_bool_compare_and_swap(&(ShortestDists[OutNId].Val), InfDepth, Depth)) {
574  PNextV->AddMP(OutNId);
575  }
576  }
577  }
578 // #pragma omp parallel for schedule(dynamic,10000)
579 // for (int NId = 0; NId < MxNId; NId++) {
580 // if (ShortestDists[NId] == InfDepth) {
581 // typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
582 // for (int e = 0; e < NI.GetInDeg(); e++) {
583 // const int InNId = NI.GetInNId(e);
584 // if (ShortestDists[InNId] < Depth) {
585 // ShortestDists[NId] = Depth;
586 // PNextV->AddMP(NId);
587 // break;
588 // }
589 // }
590 // }
591 // }
592  // swap pointer, no copying
593  TIntV* Tmp = PCurV;
594  PCurV = PNextV;
595  PNextV = Tmp;
596  // clear next
597  PNextV->Reduce(0); // reduce length, does not initialize new array
598  }
599  return Depth-1;
600 }
601 #endif // USE_OPENMP
602 
603 } // 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::BottomUpStep
bool BottomUpStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int &MaxDist, const int &TargetNId, const bool &FollowOut, const bool &FollowIn)
Definition: bfsdfs.h:262
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TBreathFS::GetHops
int GetHops(const int &SrcNId, const int &DstNId) const
Definition: bfsdfs.h:294
TBreathFS::beta
static const unsigned int beta
Definition: bfsdfs.h:113
TSnap::GetShortestDistances
int GetShortestDistances(const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, TIntV &ShortestDists)
Definition: bfsdfs.h:501
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:87
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:416
TBreathFS::TopDownStep
bool TopDownStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int &MaxDist, const int &TargetNId, const bool &FollowOut, const bool &FollowIn)
Definition: bfsdfs.h:231
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:424
TSnap::GetBfsEffDiamAll
double GetBfsEffDiamAll(const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiamX, int &FullDiamX, double &AvgSPLX)
Returns the (approximation of the) Effective Diameter, the Diameter and the Average Shortest Path len...
Definition: bfsdfs.h:467
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TInt::Mx
static const int Mx
Definition: dt.h:1139
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:128
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntFltKd
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
TBreathFS::alpha
static const unsigned int alpha
Definition: bfsdfs.h:112
TBreathFS::TBreathFS
TBreathFS(const PGraph &GraphPt, const bool &InitBigQ=true)
Definition: bfsdfs.h:90
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:387
TStdOut::New
static TPt< TSOut > New()
Definition: fl.h:266
TVec::AddMP
TSizeTy AddMP(const TVal &Val)
Adds element Val at the end of the vector in a thread safe manner, returns the element index in the v...
Definition: ds.h:617
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1143
TVec::Reduce
void Reduce(const TSizeTy &_Vals=-1)
Reduces the vector's length to _Vals elements, which must be less than the current length...
Definition: ds.h:556
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:120
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:332
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:86
TBreathFS::GetRndPath
int GetRndPath(const int &SrcNId, const int &DstNId, TIntV &PathNIdV) const
Definition: bfsdfs.h:302
THash::Swap
void Swap(THash &Hash)
Definition: hash.h:544
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
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:375
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
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:542
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
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:363
TBreathFS::Stage
int Stage
Definition: bfsdfs.h:111
TVec::SetVal
void SetVal(const TSizeTy &ValN, const TVal &Val)
Sets the value of element at position ValN to Val.
Definition: ds.h:653
TInt
Definition: dt.h:1134
TSnap::GetShortestDistancesMP2
int GetShortestDistancesMP2(const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, TIntV &ShortestDists)
Definition: bfsdfs.h:545
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:85
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TVec::Shuffle
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
TBreathFS::GetNVisited
int GetNVisited() const
Returns the number of nodes visited/reached by the BFS.
Definition: bfsdfs.h:99
THash::GetKeyDatPrV
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
TBreathFS::GetVisitedNIdV
void GetVisitedNIdV(TIntV &NIdV) const
Returns the IDs of the nodes visited/reached by the BFS.
Definition: bfsdfs.h:101
TIntV
TVec< TInt > TIntV
Definition: ds.h:1594
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1350
TBreathFS::DoBfsHybrid
int DoBfsHybrid(const int &StartNode, const bool &FollowOut, const bool &FollowIn, const int &TargetNId=-1, const int &MxDist=TInt::Mx)
Same functionality as DoBfs with better performance.
Definition: bfsdfs.h:168
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
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:602
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88
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:409
THash::Len
int Len() const
Definition: hash.h:228
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
THash::SortByDat
void SortByDat(const bool &Asc=true)
Definition: hash.h:292