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
TBreathFS< PGraph > Class Template Reference

#include <bfsdfs.h>

Collaboration diagram for TBreathFS< PGraph >:

Public Member Functions

 TBreathFS (const PGraph &GraphPt, const bool &InitBigQ=true)
 
void SetGraph (const PGraph &GraphPt)
 Sets the graph to be used by the BFS to GraphPt and resets the data structures. More...
 
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 FollowIn = true) and/or out-links (parameter FollowOut = true). More...
 
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. More...
 
int GetNVisited () const
 Returns the number of nodes visited/reached by the BFS. More...
 
void GetVisitedNIdV (TIntV &NIdV) const
 Returns the IDs of the nodes visited/reached by the BFS. More...
 
int GetHops (const int &SrcNId, const int &DstNId) const
 
int GetRndPath (const int &SrcNId, const int &DstNId, TIntV &PathNIdV) const
 

Public Attributes

PGraph Graph
 
TSnapQueue< int > Queue
 
TInt StartNId
 
TIntH NIdDistH
 

Private Member Functions

bool TopDownStep (TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int &MaxDist, const int &TargetNId, const bool &FollowOut, const bool &FollowIn)
 
bool BottomUpStep (TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int &MaxDist, const int &TargetNId, const bool &FollowOut, const bool &FollowIn)
 

Private Attributes

int Stage
 

Static Private Attributes

static const unsigned int alpha = 100
 
static const unsigned int beta = 20
 

Detailed Description

template<class PGraph>
class TBreathFS< PGraph >

Breath-First-Search class. The class is meant for executing many BFSs over a fixed graph. This means that the class can keep the hash tables and queues initialized between different calls of the DoBfs() function.

Definition at line 74 of file bfsdfs.h.

Constructor & Destructor Documentation

template<class PGraph>
TBreathFS< PGraph >::TBreathFS ( const PGraph &  GraphPt,
const bool &  InitBigQ = true 
)
inline

Definition at line 81 of file bfsdfs.h.

81  :
82  Graph(GraphPt), Queue(InitBigQ?Graph->GetNodes():1024), NIdDistH(InitBigQ?Graph->GetNodes():1024) { }
TSnapQueue< int > Queue
Definition: bfsdfs.h:77
PGraph Graph
Definition: bfsdfs.h:76
TIntH NIdDistH
Definition: bfsdfs.h:79

Member Function Documentation

template<class PGraph >
bool TBreathFS< PGraph >::BottomUpStep ( TIntV NIdDistV,
TIntV Frontier,
TIntV NextFrontier,
int &  MaxDist,
const int &  TargetNId,
const bool &  FollowOut,
const bool &  FollowIn 
)
private

Definition at line 253 of file bfsdfs.h.

References TVec< TVal, TSizeTy >::Add().

253  {
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 }
PGraph Graph
Definition: bfsdfs.h:76
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

template<class PGraph >
int TBreathFS< PGraph >::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 FollowIn = true) and/or out-links (parameter FollowOut = true).

Definition at line 119 of file bfsdfs.h.

References IAssert, and TMath::Mx().

Referenced by TSnap::TSnapDetail::CmtyGirvanNewmanStep(), TSnap::GetBfsEffDiam(), TSnap::GetBfsTree(), TSnap::GetNodeEcc(), TSnap::GetNodesAtHop(), TSnap::GetNodesAtHops(), TSnap::GetShortPath(), TSnap::GetSubTreeSz(), and TSnap::PlotShortPathDistr().

119  {
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 }
#define IAssert(Cond)
Definition: bd.h:262
TInt StartNId
Definition: bfsdfs.h:78
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void Pop()
Removes the first element from the queue.
Definition: gbase.h:198
TSnapQueue< int > Queue
Definition: bfsdfs.h:77
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:186
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:181
PGraph Graph
Definition: bfsdfs.h:76
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:201
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:196
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TIntH NIdDistH
Definition: bfsdfs.h:79
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >
int TBreathFS< PGraph >::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 at line 159 of file bfsdfs.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Empty(), IAssert, TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::SetVal().

159  {
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 }
#define IAssert(Cond)
Definition: bd.h:262
bool BottomUpStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int &MaxDist, const int &TargetNId, const bool &FollowOut, const bool &FollowIn)
Definition: bfsdfs.h:253
static const unsigned int beta
Definition: bfsdfs.h:104
TInt StartNId
Definition: bfsdfs.h:78
bool TopDownStep(TIntV &NIdDistV, TIntV *Frontier, TIntV *NextFrontier, int &MaxDist, const int &TargetNId, const bool &FollowOut, const bool &FollowIn)
Definition: bfsdfs.h:222
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static const unsigned int alpha
Definition: bfsdfs.h:103
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
int Stage
Definition: bfsdfs.h:102
void SetVal(const TSizeTy &ValN, const TVal &Val)
Sets the value of element at position ValN to Val.
Definition: ds.h:653
PGraph Graph
Definition: bfsdfs.h:76
TVec< TInt > TIntV
Definition: ds.h:1594
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TIntH NIdDistH
Definition: bfsdfs.h:79
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class PGraph >
int TBreathFS< PGraph >::GetHops ( const int &  SrcNId,
const int &  DstNId 
) const

Returns the shortst path distance between SrcNId and DistNId. Note you have to first call DoBFs(). SrcNId must be equal to StartNode, otherwise return value is -1.

Definition at line 285 of file bfsdfs.h.

References TInt::Val.

Referenced by TSnap::TSnapDetail::CmtyGirvanNewmanStep(), and TSnap::GetShortPath().

285  {
286  TInt Dist;
287  if (SrcNId!=StartNId) { return -1; }
288  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
289  return Dist.Val;
290 }
TInt StartNId
Definition: bfsdfs.h:78
int Val
Definition: dt.h:1136
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
Definition: dt.h:1134
TIntH NIdDistH
Definition: bfsdfs.h:79

Here is the caller graph for this function:

template<class PGraph>
int TBreathFS< PGraph >::GetNVisited ( ) const
inline

Returns the number of nodes visited/reached by the BFS.

Definition at line 90 of file bfsdfs.h.

References THash< TKey, TDat, THashFunc >::Len(), and TBreathFS< PGraph >::NIdDistH.

90 { return NIdDistH.Len(); }
TIntH NIdDistH
Definition: bfsdfs.h:79
int Len() const
Definition: hash.h:228

Here is the call graph for this function:

template<class PGraph >
int TBreathFS< PGraph >::GetRndPath ( const int &  SrcNId,
const int &  DstNId,
TIntV PathNIdV 
) const

Returns a random shortest path from SrcNId to DstNId. Note you have to first call DoBFs(). SrcNId must be equal to StartNode, otherwise return value is -1.

Definition at line 293 of file bfsdfs.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Empty(), TRnd::GetUniDevInt(), IAssert, TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Reverse(), and TInt::Rnd.

293  {
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 }
#define IAssert(Cond)
Definition: bd.h:262
TInt StartNId
Definition: bfsdfs.h:78
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static TRnd Rnd
Definition: dt.h:1143
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
Definition: dt.h:1134
PGraph Graph
Definition: bfsdfs.h:76
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1350
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TIntH NIdDistH
Definition: bfsdfs.h:79

Here is the call graph for this function:

template<class PGraph>
void TBreathFS< PGraph >::GetVisitedNIdV ( TIntV NIdV) const
inline

Returns the IDs of the nodes visited/reached by the BFS.

Definition at line 92 of file bfsdfs.h.

References THash< TKey, TDat, THashFunc >::GetKeyV(), and TBreathFS< PGraph >::NIdDistH.

92 { NIdDistH.GetKeyV(NIdV); }
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
TIntH NIdDistH
Definition: bfsdfs.h:79

Here is the call graph for this function:

template<class PGraph >
void TBreathFS< PGraph >::SetGraph ( const PGraph &  GraphPt)

Sets the graph to be used by the BFS to GraphPt and resets the data structures.

Definition at line 111 of file bfsdfs.h.

111  {
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 }
void Gen(const int &MxVals, const int &MaxFirst=1024)
Definition: gbase.h:182
TSnapQueue< int > Queue
Definition: bfsdfs.h:77
void Gen(const int &ExpectVals)
Definition: hash.h:222
int Reserved() const
Definition: gbase.h:193
int GetReservedKeyIds() const
Definition: hash.h:232
PGraph Graph
Definition: bfsdfs.h:76
TIntH NIdDistH
Definition: bfsdfs.h:79
template<class PGraph >
bool TBreathFS< PGraph >::TopDownStep ( TIntV NIdDistV,
TIntV Frontier,
TIntV NextFrontier,
int &  MaxDist,
const int &  TargetNId,
const bool &  FollowOut,
const bool &  FollowIn 
)
private

Definition at line 222 of file bfsdfs.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::BegI(), TVec< TVal, TSizeTy >::EndI(), IAssert, and TVec< TVal, TSizeTy >::SetVal().

222  {
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 }
#define IAssert(Cond)
Definition: bd.h:262
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
void SetVal(const TSizeTy &ValN, const TVal &Val)
Sets the value of element at position ValN to Val.
Definition: ds.h:653
Definition: dt.h:1134
PGraph Graph
Definition: bfsdfs.h:76
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Member Data Documentation

template<class PGraph>
const unsigned int TBreathFS< PGraph >::alpha = 100
staticprivate

Definition at line 103 of file bfsdfs.h.

template<class PGraph>
const unsigned int TBreathFS< PGraph >::beta = 20
staticprivate

Definition at line 104 of file bfsdfs.h.

template<class PGraph>
PGraph TBreathFS< PGraph >::Graph

Definition at line 76 of file bfsdfs.h.

template<class PGraph>
TSnapQueue<int> TBreathFS< PGraph >::Queue

Definition at line 77 of file bfsdfs.h.

template<class PGraph>
int TBreathFS< PGraph >::Stage
private

Definition at line 102 of file bfsdfs.h.

template<class PGraph>
TInt TBreathFS< PGraph >::StartNId

Definition at line 78 of file bfsdfs.h.


The documentation for this class was generated from the following file: