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
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
TBreathFS< PGraph > Class Template Reference

#include <bfsdfs.h>

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 83 of file bfsdfs.h.

Constructor & Destructor Documentation

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

Definition at line 90 of file bfsdfs.h.

90  :
91  Graph(GraphPt), Queue(InitBigQ?Graph->GetNodes():1024), NIdDistH(InitBigQ?Graph->GetNodes():1024) { }
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:86
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:85
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88

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 262 of file bfsdfs.h.

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

128  {
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:87
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TSnapQueue::Pop
void Pop()
Removes the first element from the queue.
Definition: gbase.h:211
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:86
TSnapQueue::Empty
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:199
TSnapQueue::Clr
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:194
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:85
TSnapQueue::Push
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:214
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TSnapQueue::Top
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:209
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 168 of file bfsdfs.h.

168  {
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
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
TBreathFS::beta
static const unsigned int beta
Definition: bfsdfs.h:113
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:87
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
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBreathFS::alpha
static const unsigned int alpha
Definition: bfsdfs.h:112
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
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
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:85
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::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
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 294 of file bfsdfs.h.

294  {
295  TInt Dist;
296  if (SrcNId!=StartNId) { return -1; }
297  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
298  return Dist.Val;
299 }
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:87
TInt::Val
int Val
Definition: dt.h:1139
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TInt
Definition: dt.h:1137
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88
template<class PGraph>
int TBreathFS< PGraph >::GetNVisited ( ) const
inline

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

Definition at line 99 of file bfsdfs.h.

99 { return NIdDistH.Len(); }
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88
THash::Len
int Len() const
Definition: hash.h:228
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 302 of file bfsdfs.h.

302  {
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:87
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1146
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TInt
Definition: dt.h:1137
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:85
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1350
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
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
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 101 of file bfsdfs.h.

101 { NIdDistH.GetKeyV(NIdV); }
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88
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 120 of file bfsdfs.h.

120  {
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 }
TSnapQueue::Gen
void Gen(const int &MxVals, const int &MaxFirst=1024)
Definition: gbase.h:195
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:86
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:222
TSnapQueue::Reserved
int Reserved() const
Definition: gbase.h:206
THash::GetReservedKeyIds
int GetReservedKeyIds() const
Definition: hash.h:232
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:85
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:88
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 231 of file bfsdfs.h.

231  {
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
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
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::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Member Data Documentation

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

Definition at line 112 of file bfsdfs.h.

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

Definition at line 113 of file bfsdfs.h.

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

Definition at line 85 of file bfsdfs.h.

template<class PGraph>
TIntH TBreathFS< PGraph >::NIdDistH

Definition at line 88 of file bfsdfs.h.

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

Definition at line 86 of file bfsdfs.h.

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

Definition at line 111 of file bfsdfs.h.

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

Definition at line 87 of file bfsdfs.h.

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