SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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
TSnap
Main namespace for all the Snap global entities.
Definition: alg.h:1
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:1139
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TInt::Mx
static const int Mx
Definition: dt.h:1142
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
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1146
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
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
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:1137
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
TPt
Definition: bd.h:196
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