SNAP Library 2.4, User Reference  2015-05-11 19:40:56
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 | 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 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
 

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

108  {
109  StartNId = StartNode;
110  IAssert(Graph->IsNode(StartNId));
111 // const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
112 // IAssertR(StartNodeI.GetOutDeg() > 0, TStr::Fmt("No neighbors from start node %d.", StartNode));
113  NIdDistH.Clr(false); NIdDistH.AddDat(StartNId, 0);
114  Queue.Clr(false); Queue.Push(StartNId);
115  int v, MaxDist = 0;
116  while (! Queue.Empty()) {
117  const int NId = Queue.Top(); Queue.Pop();
118  const int Dist = NIdDistH.GetDat(NId);
119  if (Dist == MxDist) { break; } // max distance limit reached
120  const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
121  if (FollowOut) { // out-links
122  for (v = 0; v < NodeI.GetOutDeg(); v++) { // out-links
123  const int DstNId = NodeI.GetOutNId(v);
124  if (! NIdDistH.IsKey(DstNId)) {
125  NIdDistH.AddDat(DstNId, Dist+1);
126  MaxDist = TMath::Mx(MaxDist, Dist+1);
127  if (DstNId == TargetNId) { return MaxDist; }
128  Queue.Push(DstNId);
129  }
130  }
131  }
132  if (FollowIn) { // in-links
133  for (v = 0; v < NodeI.GetInDeg(); v++) {
134  const int DstNId = NodeI.GetInNId(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  }
144  return MaxDist;
145 }
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:195
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:183
TSnapQueue::Clr
void Clr(const bool &DoDel=true)
Deletes all elements from the queue.
Definition: gbase.h:178
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:198
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:315
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:193
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 >::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 148 of file bfsdfs.h.

148  {
149  TInt Dist;
150  if (SrcNId!=StartNId) { return -1; }
151  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
152  return Dist.Val;
153 }
TBreathFS::StartNId
TInt StartNId
Definition: bfsdfs.h:78
TInt::Val
int Val
Definition: dt.h:1044
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:228
TInt
Definition: dt.h:1042
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 88 of file bfsdfs.h.

88 { 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 156 of file bfsdfs.h.

156  {
157  PathNIdV.Clr(false);
158  if (SrcNId!=StartNId || ! NIdDistH.IsKey(DstNId)) { return -1; }
159  PathNIdV.Add(DstNId);
160  TIntV CloserNIdV;
161  int CurNId = DstNId;
162  TInt CurDist, NextDist;
163  while (CurNId != SrcNId) {
164  typename PGraph::TObj::TNodeI NI = Graph->GetNI(CurNId);
165  IAssert(NIdDistH.IsKeyGetDat(CurNId, CurDist));
166  CloserNIdV.Clr(false);
167  for (int e = 0; e < NI.GetDeg(); e++) {
168  const int Next = NI.GetNbrNId(e);
169  if (NIdDistH.IsKeyGetDat(Next, NextDist)) {
170  if (NextDist == CurDist-1) { CloserNIdV.Add(Next); }
171  }
172  }
173  IAssert(! CloserNIdV.Empty());
174  CurNId = CloserNIdV[TInt::Rnd.GetUniDevInt(CloserNIdV.Len())];
175  PathNIdV.Add(CurNId);
176  }
177  PathNIdV.Reverse();
178  return PathNIdV.Len()-1;
179 }
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:535
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1051
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:228
TInt
Definition: dt.h:1042
TBreathFS::Graph
PGraph Graph
Definition: bfsdfs.h:76
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1250
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:559
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 90 of file bfsdfs.h.

90 { NIdDistH.GetKeyV(NIdV); }
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:438
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 100 of file bfsdfs.h.

100  {
101  Graph=GraphPt;
102  const int N=GraphPt->GetNodes();
103  if (Queue.Reserved() < N) { Queue.Gen(N); }
104  if (NIdDistH.GetReservedKeyIds() < N) { NIdDistH.Gen(N); }
105 }
TSnapQueue::Gen
void Gen(const int &MxVals, const int &MaxFirst=1024)
Definition: gbase.h:179
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:190
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

Member Data Documentation

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>
TInt TBreathFS< PGraph >::StartNId

Definition at line 78 of file bfsdfs.h.

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