TBreathFS< PGraph > Class Template Reference

#include <bfsdfs.h>

List of all members.

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.
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).
int	GetNVisited () const
	Returns the number of nodes visited/reached by the BFS.
void	GetVisitedNIdV (TIntV &NIdV) const
	Returns the IDs of the nodes visited/reached by the BFS.
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.

                                                              :
    Graph(GraphPt), Queue(InitBigQ?Graph->GetNodes():1024), NIdDistH(InitBigQ?Graph->GetNodes():1024) { }

---

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.

                                                                                                                                       {
  StartNId = StartNode;
  IAssert(Graph->IsNode(StartNId));
//  const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
//  IAssertR(StartNodeI.GetOutDeg() > 0, TStr::Fmt("No neighbors from start node %d.", StartNode));
  NIdDistH.Clr(false);  NIdDistH.AddDat(StartNId, 0);
  Queue.Clr(false);  Queue.Push(StartNId);
  int v, MaxDist = 0;
  while (! Queue.Empty()) {
    const int NId = Queue.Top();  Queue.Pop();
    const int Dist = NIdDistH.GetDat(NId);
    if (Dist == MxDist) { break; } // max distance limit reached
    const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
    if (FollowOut) { // out-links
      for (v = 0; v < NodeI.GetOutDeg(); v++) {  // out-links
        const int DstNId = NodeI.GetOutNId(v);
        if (! NIdDistH.IsKey(DstNId)) {
          NIdDistH.AddDat(DstNId, Dist+1);
          MaxDist = TMath::Mx(MaxDist, Dist+1);
          if (DstNId == TargetNId) { return MaxDist; }
          Queue.Push(DstNId);
        }
      }
    }
    if (FollowIn) { // in-links
      for (v = 0; v < NodeI.GetInDeg(); v++) {
        const int DstNId = NodeI.GetInNId(v);
        if (! NIdDistH.IsKey(DstNId)) {
          NIdDistH.AddDat(DstNId, Dist+1);
          MaxDist = TMath::Mx(MaxDist, Dist+1);
          if (DstNId == TargetNId) { return MaxDist; }
          Queue.Push(DstNId);
        }
      }
    }
  }
  return MaxDist;
}

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.

                                                                         {
  TInt Dist;
  if (SrcNId!=StartNId) { return -1; }
  if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
  return Dist.Val;
}

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.

{ return NIdDistH.Len(); }

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.

                                                                                             {
  PathNIdV.Clr(false);
  if (SrcNId!=StartNId || ! NIdDistH.IsKey(DstNId)) { return -1; }
  PathNIdV.Add(DstNId);
  TIntV CloserNIdV;
  int CurNId = DstNId;
  TInt CurDist, NextDist;
  while (CurNId != SrcNId) {
    typename PGraph::TObj::TNodeI NI = Graph->GetNI(CurNId);
    IAssert(NIdDistH.IsKeyGetDat(CurNId, CurDist));
    CloserNIdV.Clr(false);
    for (int e = 0; e < NI.GetDeg(); e++) {
      const int Next = NI.GetNbrNId(e);
      IAssert(NIdDistH.IsKeyGetDat(Next, NextDist));
      if (NextDist == CurDist-1) { CloserNIdV.Add(Next); }
    }
    IAssert(! CloserNIdV.Empty());
    CurNId = CloserNIdV[TInt::Rnd.GetUniDevInt(CloserNIdV.Len())];
    PathNIdV.Add(CurNId);
  }
  PathNIdV.Reverse();
  return PathNIdV.Len()-1;
}

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.

{ NIdDistH.GetKeyV(NIdV); }

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.

                                                      {
  Graph=GraphPt;
  const int N=GraphPt->GetNodes();
  if (Queue.Reserved() < N) { Queue.Gen(N); }
  if (NIdDistH.GetReservedKeyIds() < N) { NIdDistH.Gen(N); }
}

---

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:

• snap-core/bfsdfs.h