#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.
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.

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().

                                                                                                                                       {
  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;
}

Here is the call graph for this function:

Here is the caller 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 148 of file bfsdfs.h.

References TInt::Val.

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

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

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

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

{ return NIdDistH.Len(); }

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 156 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.

                                                                                             {
  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;
}

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

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

{ NIdDistH.GetKeyV(NIdV); }

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 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); }
}