SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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
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 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) { }
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:77
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
TBreathFS::NIdDistH
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.

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

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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:78
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:220
TSnapQueue::Pop
void Pop()
Removes the first element from the queue.
Definition: gbase.h:198
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:77
TSnapQueue::Empty
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:186
TSnapQueue::Clr
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:181
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
TSnapQueue::Push
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:201
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
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:196
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
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.

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 }
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:253
TBreathFS::beta
static const unsigned int beta
Definition: bfsdfs.h:104
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:78
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
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TBreathFS::alpha
static const unsigned int alpha
Definition: bfsdfs.h:103
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
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:625
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
TIntV
TVec< TInt > TIntV
Definition: ds.h:1529
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
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.

285  {
286  TInt Dist;
287  if (SrcNId!=StartNId) { return -1; }
288  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
289  return Dist.Val;
290 }
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:78
TInt::Val
int Val
Definition: dt.h:1046
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:232
TInt
Definition: dt.h:1044
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
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.

90 { return NIdDistH.Len(); }
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
THash::Len
int Len() const
Definition: hash.h:186
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.

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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:78
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1053
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:232
TInt
Definition: dt.h:1044
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1286
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
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.

92 { NIdDistH.GetKeyV(NIdV); }
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:442
TBreathFS::NIdDistH
TIntH NIdDistH
Definition: bfsdfs.h:79
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 }
TSnapQueue::Gen
void Gen(const int &MxVals, const int &MaxFirst=1024)
Definition: gbase.h:182
TBreathFS::Queue
TSnapQueue< int > Queue
Definition: bfsdfs.h:77
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:180
TSnapQueue::Reserved
int Reserved() const
Definition: gbase.h:193
THash::GetReservedKeyIds
int GetReservedKeyIds() const
Definition: hash.h:190
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
TBreathFS::NIdDistH
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.

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 }
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:567
TVec::SetVal
void SetVal(const TSizeTy &ValN, const TVal &Val)
Sets the value of element at position ValN to Val.
Definition: ds.h:625
TInt
Definition: dt.h:1044
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:565
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574

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>
TIntH TBreathFS< PGraph >::NIdDistH

Definition at line 79 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: