SNAP Library 2.0, User Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
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: