SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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 DoBfsHybrid(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId=-1, const int& MxDist=TInt::Mx);
90  int GetNVisited() const { return NIdDistH.Len(); }
92  void GetVisitedNIdV(TIntV& NIdV) const { NIdDistH.GetKeyV(NIdV); }
95  int GetHops(const int& SrcNId, const int& DstNId) const;
98  int GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const;
99 
100 /* Private variables and functions for DoBfsHybrid */
101 private:
102  int Stage; // 0, 2: top down, 1: bottom up
103  static const unsigned int alpha = 100;
104  static const unsigned int beta = 20;
105  /* Private functions */
106  bool TopDownStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn);
107  bool BottomUpStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn);
108 };
109 
110 template<class PGraph>
111 void TBreathFS<PGraph>::SetGraph(const PGraph& GraphPt) {
112  Graph=GraphPt;
113  const int N=GraphPt->GetNodes();
114  if (Queue.Reserved() < N) { Queue.Gen(N); }
115  if (NIdDistH.GetReservedKeyIds() < N) { NIdDistH.Gen(N); }
116 }
117 
118 template<class PGraph>
119 int TBreathFS<PGraph>::DoBfs(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId, const int& MxDist) {
120  StartNId = StartNode;
121  IAssert(Graph->IsNode(StartNId));
122 // const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
123 // IAssertR(StartNodeI.GetOutDeg() > 0, TStr::Fmt("No neighbors from start node %d.", StartNode));
124  NIdDistH.Clr(false); NIdDistH.AddDat(StartNId, 0);
125  Queue.Clr(false); Queue.Push(StartNId);
126  int v, MaxDist = 0;
127  while (! Queue.Empty()) {
128  const int NId = Queue.Top(); Queue.Pop();
129  const int Dist = NIdDistH.GetDat(NId);
130  if (Dist == MxDist) { break; } // max distance limit reached
131  const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
132  if (FollowOut) { // out-links
133  for (v = 0; v < NodeI.GetOutDeg(); v++) { // out-links
134  const int DstNId = NodeI.GetOutNId(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  if (FollowIn) { // in-links
144  for (v = 0; v < NodeI.GetInDeg(); v++) {
145  const int DstNId = NodeI.GetInNId(v);
146  if (! NIdDistH.IsKey(DstNId)) {
147  NIdDistH.AddDat(DstNId, Dist+1);
148  MaxDist = TMath::Mx(MaxDist, Dist+1);
149  if (DstNId == TargetNId) { return MaxDist; }
150  Queue.Push(DstNId);
151  }
152  }
153  }
154  }
155  return MaxDist;
156 }
157 
158 template<class PGraph>
159 int TBreathFS<PGraph>::DoBfsHybrid(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId, const int& MxDist) {
160  StartNId = StartNode;
161  IAssert(Graph->IsNode(StartNId));
162  if (TargetNId == StartNode) return 0;
163  const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
164 
165  // Initialize vector
166  TIntV NIdDistV(Graph->GetMxNId() + 1);
167  for (int i = 0; i < NIdDistV.Len(); i++) {
168  NIdDistV.SetVal(i, -1);
169  }
170  TIntV *Frontier = new TIntV(Graph->GetNodes(), 0);
171  TIntV *NextFrontier = new TIntV(Graph->GetNodes(), 0);
172 
173  NIdDistV.SetVal(StartNId, 0);
174  Frontier->Add(StartNId);
175  Stage = 0;
176  int MaxDist = -1;
177  const unsigned int TotalNodes = Graph->GetNodes();
178  unsigned int UnvisitedNodes = Graph->GetNodes();
179  while (! Frontier->Empty()) {
180  MaxDist += 1;
181  NextFrontier->Clr(false);
182  if (MaxDist == MxDist) { break; } // max distance limit reached
183 
184  UnvisitedNodes -= Frontier->Len();
185  if (Stage == 0 && UnvisitedNodes / Frontier->Len() < alpha) {
186  Stage = 1;
187  } else if (Stage == 1 && TotalNodes / Frontier->Len() > beta) {
188  Stage = 2;
189  }
190 
191  // Top down or bottom up depending on stage
192  bool targetFound = false;
193  if (Stage == 0 || Stage == 2) {
194  targetFound = TopDownStep(NIdDistV, Frontier, NextFrontier, MaxDist, TargetNId, FollowOut, FollowIn);
195  } else {
196  targetFound = BottomUpStep(NIdDistV, Frontier, NextFrontier, MaxDist, TargetNId, FollowOut, FollowIn);
197  }
198  if (targetFound) {
199  MaxDist = NIdDistV[TargetNId];
200  break;
201  }
202 
203  // swap Frontier and NextFrontier
204  TIntV *temp = Frontier;
205  Frontier = NextFrontier;
206  NextFrontier = temp;
207  }
208 
209  delete Frontier;
210  delete NextFrontier;
211  // Transform vector to hash table
212  NIdDistH.Clr(false);
213  for (int NId = 0; NId < NIdDistV.Len(); NId++) {
214  if (NIdDistV[NId] != -1) {
215  NIdDistH.AddDat(NId, NIdDistV[NId]);
216  }
217  }
218  return MaxDist;
219 }
220 
221 template<class PGraph>
222 bool TBreathFS<PGraph>::TopDownStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn) {
223  for (TIntV::TIter it = Frontier->BegI(); it != Frontier->EndI(); ++it) { // loop over frontier
224  const int NId = *it;
225  const int Dist = NIdDistV[NId];
226  IAssert(Dist == MaxDist); // Must equal to MaxDist
227  const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
228  if (FollowOut) {
229  for (int v = 0; v < NodeI.GetOutDeg(); v++) {
230  const int NeighborNId = NodeI.GetOutNId(v);
231  if (NIdDistV[NeighborNId] == -1) {
232  NIdDistV.SetVal(NeighborNId, Dist+1);
233  if (NeighborNId == TargetNId) return true;
234  NextFrontier->Add(NeighborNId);
235  }
236  }
237  }
238  if (FollowIn) {
239  for (int v = 0; v < NodeI.GetInDeg(); v++) {
240  const int NeighborNId = NodeI.GetInNId(v);
241  if (NIdDistV[NeighborNId] == -1) {
242  NIdDistV.SetVal(NeighborNId, Dist+1);
243  if (NeighborNId == TargetNId) return true;
244  NextFrontier->Add(NeighborNId);
245  }
246  }
247  }
248  }
249  return false;
250 }
251 
252 template<class PGraph>
253 bool TBreathFS<PGraph>::BottomUpStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int& MaxDist, const int& TargetNId, const bool& FollowOut, const bool& FollowIn) {
254  for (typename PGraph::TObj::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
255  const int NId = NodeI.GetId();
256  if (NIdDistV[NId] == -1) {
257  if (FollowOut) {
258  for (int v = 0; v < NodeI.GetInDeg(); v++) {
259  const int ParentNId = NodeI.GetInNId(v);
260  if (NIdDistV[ParentNId] == MaxDist) {
261  NIdDistV[NId] = MaxDist + 1;
262  if (NId == TargetNId) return true;
263  NextFrontier->Add(NId);
264  break;
265  }
266  }
267  }
268  if (FollowIn && NIdDistV[NId] == -1) {
269  for (int v = 0; v < NodeI.GetOutDeg(); v++) {
270  const int ParentNId = NodeI.GetOutNId(v);
271  if (NIdDistV[ParentNId] == MaxDist) {
272  NIdDistV[NId] = MaxDist + 1;
273  if (NId == TargetNId) return true;
274  NextFrontier->Add(NId);
275  break;
276  }
277  }
278  }
279  }
280  }
281  return false;
282 }
283 
284 template<class PGraph>
285 int TBreathFS<PGraph>::GetHops(const int& SrcNId, const int& DstNId) const {
286  TInt Dist;
287  if (SrcNId!=StartNId) { return -1; }
288  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
289  return Dist.Val;
290 }
291 
292 template<class PGraph>
293 int TBreathFS<PGraph>::GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const {
294  PathNIdV.Clr(false);
295  if (SrcNId!=StartNId || ! NIdDistH.IsKey(DstNId)) { return -1; }
296  PathNIdV.Add(DstNId);
297  TIntV CloserNIdV;
298  int CurNId = DstNId;
299  TInt CurDist, NextDist;
300  while (CurNId != SrcNId) {
301  typename PGraph::TObj::TNodeI NI = Graph->GetNI(CurNId);
302  IAssert(NIdDistH.IsKeyGetDat(CurNId, CurDist));
303  CloserNIdV.Clr(false);
304  for (int e = 0; e < NI.GetDeg(); e++) {
305  const int Next = NI.GetNbrNId(e);
306  if (NIdDistH.IsKeyGetDat(Next, NextDist)) {
307  if (NextDist == CurDist-1) { CloserNIdV.Add(Next); }
308  }
309  }
310  IAssert(! CloserNIdV.Empty());
311  CurNId = CloserNIdV[TInt::Rnd.GetUniDevInt(CloserNIdV.Len())];
312  PathNIdV.Add(CurNId);
313  }
314  PathNIdV.Reverse();
315  return PathNIdV.Len()-1;
316 }
317 
319 // Implementation
320 namespace TSnap {
321 
322 template <class PGraph>
323 PNGraph GetBfsTree(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn) {
324  TBreathFS<PGraph> BFS(Graph);
325  BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
326  PNGraph Tree = TNGraph::New();
327  BFS.NIdDistH.SortByDat();
328  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
329  const int NId = BFS.NIdDistH.GetKey(i);
330  const int Dist = BFS.NIdDistH[i];
331  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
332  if (!Tree->IsNode(NId)) {
333  Tree->AddNode(NId);
334  }
335  if (FollowOut) {
336  for (int e = 0; e < NI.GetInDeg(); e++) {
337  const int Prev = NI.GetInNId(e);
338  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
339  Tree->AddEdge(Prev, NId); }
340  }
341  }
342  if (FollowIn) {
343  for (int e = 0; e < NI.GetOutDeg(); e++) {
344  const int Prev = NI.GetOutNId(e);
345  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
346  Tree->AddEdge(Prev, NId); }
347  }
348  }
349  }
350  return Tree;
351 }
352 
353 template <class PGraph>
354 int GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, int& TreeSz, int& TreeDepth) {
355  TBreathFS<PGraph> BFS(Graph);
356  BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
357  TreeSz = BFS.NIdDistH.Len();
358  TreeDepth = 0;
359  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
360  TreeDepth = TMath::Mx(TreeDepth, BFS.NIdDistH[i].Val);
361  }
362  return TreeSz;
363 }
364 
365 template <class PGraph>
366 int GetNodesAtHop(const PGraph& Graph, const int& StartNId, const int& Hop, TIntV& NIdV, const bool& IsDir) {
367  TBreathFS<PGraph> BFS(Graph);
368  BFS.DoBfs(StartNId, true, !IsDir, -1, Hop);
369  NIdV.Clr(false);
370  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
371  if (BFS.NIdDistH[i] == Hop) {
372  NIdV.Add(BFS.NIdDistH.GetKey(i)); }
373  }
374  return NIdV.Len();
375 }
376 
377 template <class PGraph>
378 int GetNodesAtHops(const PGraph& Graph, const int& StartNId, TIntPrV& HopCntV, const bool& IsDir) {
379  TBreathFS<PGraph> BFS(Graph);
380  BFS.DoBfs(StartNId, true, !IsDir, -1, TInt::Mx);
381  TIntH HopCntH;
382  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
383  HopCntH.AddDat(BFS.NIdDistH[i]) += 1;
384  }
385  HopCntH.GetKeyDatPrV(HopCntV);
386  HopCntV.Sort();
387  return HopCntV.Len();
388 }
389 
390 template <class PGraph>
391 int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir, const int& MaxDist) {
392  TBreathFS<PGraph> BFS(Graph);
393  BFS.DoBfs(SrcNId, true, ! IsDir, -1, MaxDist);
394  NIdToDistH.Clr();
395  NIdToDistH.Swap(BFS.NIdDistH);
396  return NIdToDistH[NIdToDistH.Len()-1];
397 }
398 
399 template <class PGraph>
400 int GetShortPath(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir) {
401  TBreathFS<PGraph> BFS(Graph);
402  BFS.DoBfs(SrcNId, true, ! IsDir, DstNId, TInt::Mx);
403  return BFS.GetHops(SrcNId, DstNId);
404 }
405 
406 template <class PGraph>
407 int GetBfsFullDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
408  int FullDiam;
409  double EffDiam;
410  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
411  return FullDiam;
412 }
413 
414 template <class PGraph>
415 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
416  int FullDiam;
417  double EffDiam;
418  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
419  return EffDiam;
420 }
421 
422 template <class PGraph>
423 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam) {
424  double AvgDiam;
425  EffDiam = -1; FullDiam = -1;
426  return GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam, AvgDiam);
427 }
428 
429 template <class PGraph>
430 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam, double& AvgSPL) {
431  EffDiam = -1; FullDiam = -1; AvgSPL = -1;
432  TIntFltH DistToCntH;
433  TBreathFS<PGraph> BFS(Graph);
434  // shotest paths
435  TIntV NodeIdV;
436  Graph->GetNIdV(NodeIdV); NodeIdV.Shuffle(TInt::Rnd);
437  for (int tries = 0; tries < TMath::Mn(NTestNodes, Graph->GetNodes()); tries++) {
438  const int NId = NodeIdV[tries];
439  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
440  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
441  DistToCntH.AddDat(BFS.NIdDistH[i]) += 1; }
442  }
443  TIntFltKdV DistNbrsPdfV;
444  double SumPathL=0, PathCnt=0;
445  for (int i = 0; i < DistToCntH.Len(); i++) {
446  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
447  SumPathL += DistToCntH.GetKey(i) * DistToCntH[i];
448  PathCnt += DistToCntH[i];
449  }
450  DistNbrsPdfV.Sort();
451  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
452  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
453  AvgSPL = SumPathL/PathCnt; // average shortest path length
454  return EffDiam;
455 }
456 
457 template <class PGraph>
458 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const TIntV& SubGraphNIdV, const bool& IsDir, double& EffDiam, int& FullDiam) {
459  EffDiam = -1;
460  FullDiam = -1;
461 
462  TIntFltH DistToCntH;
463  TBreathFS<PGraph> BFS(Graph);
464  // shotest paths
465  TIntV NodeIdV(SubGraphNIdV); NodeIdV.Shuffle(TInt::Rnd);
466  TInt Dist;
467  for (int tries = 0; tries < TMath::Mn(NTestNodes, SubGraphNIdV.Len()); tries++) {
468  const int NId = NodeIdV[tries];
469  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
470  for (int i = 0; i < SubGraphNIdV.Len(); i++) {
471  if (BFS.NIdDistH.IsKeyGetDat(SubGraphNIdV[i], Dist)) {
472  DistToCntH.AddDat(Dist) += 1;
473  }
474  }
475  }
476  TIntFltKdV DistNbrsPdfV;
477  for (int i = 0; i < DistToCntH.Len(); i++) {
478  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
479  }
480  DistNbrsPdfV.Sort();
481  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
482  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
483  return EffDiam; // average shortest path length
484 }
485 
486 template <class PGraph>
487 int GetShortestDistances(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, TIntV& ShortestDists) {
488  PSOut StdOut = TStdOut::New();
489  int MxNId = Graph->GetMxNId();
490  int NonNodeDepth = 2147483647; // INT_MAX
491  int InfDepth = 2147483646; // INT_MAX - 1
492  ShortestDists.Gen(MxNId);
493  for (int NId = 0; NId < MxNId; NId++) {
494  if (Graph->IsNode(NId)) { ShortestDists[NId] = InfDepth; }
495  else { ShortestDists[NId] = NonNodeDepth; }
496  }
497 
498  TIntV Vec1(MxNId, 0); // ensure enough capacity
499  TIntV Vec2(MxNId, 0); // ensure enough capacity
500 
501  ShortestDists[StartNId] = 0;
502  TIntV* PCurV = &Vec1;
503  PCurV->Add(StartNId);
504  TIntV* PNextV = &Vec2;
505  int Depth = 0; // current depth
506  while (!PCurV->Empty()) {
507  Depth++; // increase depth
508  for (int i = 0; i < PCurV->Len(); i++) {
509  int NId = PCurV->GetVal(i);
510  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
511  for (int e = 0; e < NI.GetOutDeg(); e++) {
512  const int OutNId = NI.GetOutNId(e);
513  if (ShortestDists[OutNId].Val == InfDepth) {
514  ShortestDists[OutNId] = Depth;
515  PNextV->Add(OutNId);
516  }
517  }
518  }
519  // swap pointer, no copying
520  TIntV* Tmp = PCurV;
521  PCurV = PNextV;
522  PNextV = Tmp;
523  // clear next
524  PNextV->Reduce(0); // reduce length, does not initialize new array
525  }
526  return Depth-1;
527 }
528 
529 #ifdef USE_OPENMP
530 template <class PGraph>
531 int GetShortestDistancesMP2(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, TIntV& ShortestDists) {
532  int MxNId = Graph->GetMxNId();
533  int NonNodeDepth = 2147483647; // INT_MAX
534  int InfDepth = 2147483646; // INT_MAX - 1
535  ShortestDists.Gen(MxNId);
536  #pragma omp parallel for schedule(dynamic,10000)
537  for (int NId = 0; NId < MxNId; NId++) {
538  if (Graph->IsNode(NId)) { ShortestDists[NId] = InfDepth; }
539  else { ShortestDists[NId] = NonNodeDepth; }
540  }
541 
542  TIntV Vec1(MxNId, 0); // ensure enough capacity
543  TIntV Vec2(MxNId, 0); // ensure enough capacity
544 
545  ShortestDists[StartNId] = 0;
546  TIntV* PCurV = &Vec1;
547  PCurV->Add(StartNId);
548  TIntV* PNextV = &Vec2;
549  int Depth = 0; // current depth
550 
551  while (!PCurV->Empty()) {
552  Depth++; // increase depth
553  #pragma omp parallel for schedule(dynamic,10000)
554  for (int i = 0; i < PCurV->Len(); i++) {
555  int NId = PCurV->GetVal(i);
556  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
557  for (int e = 0; e < NI.GetOutDeg(); e++) {
558  const int OutNId = NI.GetOutNId(e);
559  if (__sync_bool_compare_and_swap(&(ShortestDists[OutNId].Val), InfDepth, Depth)) {
560  PNextV->AddMP(OutNId);
561  }
562  }
563  }
564 // #pragma omp parallel for schedule(dynamic,10000)
565 // for (int NId = 0; NId < MxNId; NId++) {
566 // if (ShortestDists[NId] == InfDepth) {
567 // typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
568 // for (int e = 0; e < NI.GetInDeg(); e++) {
569 // const int InNId = NI.GetInNId(e);
570 // if (ShortestDists[InNId] < Depth) {
571 // ShortestDists[NId] = Depth;
572 // PNextV->AddMP(NId);
573 // break;
574 // }
575 // }
576 // }
577 // }
578  // swap pointer, no copying
579  TIntV* Tmp = PCurV;
580  PCurV = PNextV;
581  PNextV = Tmp;
582  // clear next
583  PNextV->Reduce(0); // reduce length, does not initialize new array
584  }
585  return Depth-1;
586 }
587 #endif // USE_OPENMP
588 
589 } // 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:253
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:285
TBreathFS::beta
static const unsigned int beta
Definition: bfsdfs.h:104
TSnap::GetShortestDistances
int GetShortestDistances(const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, TIntV &ShortestDists)
Definition: bfsdfs.h:487
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:407
TBreathFS::TopDownStep
bool TopDownStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int &MaxDist, const int &TargetNId, const bool &FollowOut, const bool &FollowIn)
Definition: bfsdfs.h:222
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:415
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:119
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:103
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:378
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:111
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:323
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
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:293
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:366
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:354
TBreathFS::Stage
int Stage
Definition: bfsdfs.h:102
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:531
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
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:90
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:92
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:159
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: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:400
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