SNAP Library 2.2, User Reference  2014-03-11 19:15:55
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
bfsdfs.h
Go to the documentation of this file.
00001 namespace TSnap {
00002 
00004 // BFS and DFS
00006 
00009 template <class PGraph> PNGraph GetBfsTree(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn);
00011 template <class PGraph> int GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, int& TreeSzX, int& TreeDepthX);
00013 
00015 template <class PGraph> int GetNodesAtHop(const PGraph& Graph, const int& StartNId, const int& Hop, TIntV& NIdV, const bool& IsDir=false);
00017 
00019 template <class PGraph> int GetNodesAtHops(const PGraph& Graph, const int& StartNId, TIntPrV& HopCntV, const bool& IsDir=false);
00020 
00022 // Shortest paths
00024 
00026 template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir=false);
00028 
00032 template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir=false, const int& MaxDist=TInt::Mx);
00033 
00035 // Diameter
00036 
00038 
00040 template <class PGraph> int GetBfsFullDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir=false);
00042 
00044 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir=false);
00046 
00048 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiamX, int& FullDiamX);
00050 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiamX, int& FullDiamX, double& AvgSPLX);
00052 template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const TIntV& SubGraphNIdV, const bool& IsDir, double& EffDiamX, int& FullDiamX);
00053 
00054 // TODO: Implement in the future
00055 //template <class PGraph> int GetRangeDist(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir=false);
00056 //template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir=false, const int& MaxDist=1000);
00057 //template <class PGraph> int GetShortPath(const PGraph& Graph, const int& SrcNId, const TIntSet& TargetSet, const bool& IsDir, TIntV& PathNIdV);
00058 //template <class PGraph> int GetShortPath(TIntH& NIdPrnH, TCcQueue<int>& NIdQ, const PGraph& Graph, const int& SrcNId, const TIntSet& TargetSet, const bool& IsDir, TIntV& PathNIdV);
00059 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir=false);
00060 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, int& MxDistNId);
00061 //template <class PGraph> int GetMxShortDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, int& MxDistNId, TCcQueue<int>& NIdQ, TCcQueue<int>& DistQ, TIntSet& VisitedH);
00062 //template <class PGraph> int GetMxGreedyDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir=false);
00063 //template <class PGraph> int GetMxGreedyDist(const PGraph& Graph, const int& SrcNId, const bool& IsDir, TCcQueue<int>& NIdQ, TCcQueue<int>& DistQ, TIntSet& VisitedH);
00064 //template <class PGraph> PNGraph GetShortPathsSubGraph(const PGraph& Graph, const TIntV& SubGraphNIdV);
00065 //template <class PGraph> PGraph GetWccPathsSubGraph(const PGraph& Graph, const TIntV& NIdV);
00066 //template <class PGraph> void GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOutEdges, int& TreeSz, int& TreeDepth);
00067 
00068 } // namespace TSnap
00069 
00070 //#//////////////////////////////////////////////
00073 template<class PGraph>
00074 class TBreathFS {
00075 public:
00076   PGraph Graph;
00077   TSnapQueue<int> Queue;
00078   TInt StartNId;
00079   TIntH NIdDistH;
00080 public:
00081   TBreathFS(const PGraph& GraphPt, const bool& InitBigQ=true) :
00082     Graph(GraphPt), Queue(InitBigQ?Graph->GetNodes():1024), NIdDistH(InitBigQ?Graph->GetNodes():1024) { }
00084   void SetGraph(const PGraph& GraphPt);
00086   int DoBfs(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId=-1, const int& MxDist=TInt::Mx);
00088   int GetNVisited() const { return NIdDistH.Len(); }
00090   void GetVisitedNIdV(TIntV& NIdV) const { NIdDistH.GetKeyV(NIdV); }
00093   int GetHops(const int& SrcNId, const int& DstNId) const;
00096   int GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const;
00097 };
00098 
00099 template<class PGraph>
00100 void TBreathFS<PGraph>::SetGraph(const PGraph& GraphPt) {
00101   Graph=GraphPt;
00102   const int N=GraphPt->GetNodes();
00103   if (Queue.Reserved() < N) { Queue.Gen(N); }
00104   if (NIdDistH.GetReservedKeyIds() < N) { NIdDistH.Gen(N); }
00105 }
00106 
00107 template<class PGraph>
00108 int TBreathFS<PGraph>::DoBfs(const int& StartNode, const bool& FollowOut, const bool& FollowIn, const int& TargetNId, const int& MxDist) {
00109   StartNId = StartNode;
00110   IAssert(Graph->IsNode(StartNId));
00111 //  const typename PGraph::TObj::TNodeI StartNodeI = Graph->GetNI(StartNode);
00112 //  IAssertR(StartNodeI.GetOutDeg() > 0, TStr::Fmt("No neighbors from start node %d.", StartNode));
00113   NIdDistH.Clr(false);  NIdDistH.AddDat(StartNId, 0);
00114   Queue.Clr(false);  Queue.Push(StartNId);
00115   int v, MaxDist = 0;
00116   while (! Queue.Empty()) {
00117     const int NId = Queue.Top();  Queue.Pop();
00118     const int Dist = NIdDistH.GetDat(NId);
00119     if (Dist == MxDist) { break; } // max distance limit reached
00120     const typename PGraph::TObj::TNodeI NodeI = Graph->GetNI(NId);
00121     if (FollowOut) { // out-links
00122       for (v = 0; v < NodeI.GetOutDeg(); v++) {  // out-links
00123         const int DstNId = NodeI.GetOutNId(v);
00124         if (! NIdDistH.IsKey(DstNId)) {
00125           NIdDistH.AddDat(DstNId, Dist+1);
00126           MaxDist = TMath::Mx(MaxDist, Dist+1);
00127           if (DstNId == TargetNId) { return MaxDist; }
00128           Queue.Push(DstNId);
00129         }
00130       }
00131     }
00132     if (FollowIn) { // in-links
00133       for (v = 0; v < NodeI.GetInDeg(); v++) {
00134         const int DstNId = NodeI.GetInNId(v);
00135         if (! NIdDistH.IsKey(DstNId)) {
00136           NIdDistH.AddDat(DstNId, Dist+1);
00137           MaxDist = TMath::Mx(MaxDist, Dist+1);
00138           if (DstNId == TargetNId) { return MaxDist; }
00139           Queue.Push(DstNId);
00140         }
00141       }
00142     }
00143   }
00144   return MaxDist;
00145 }
00146 
00147 template<class PGraph>
00148 int TBreathFS<PGraph>::GetHops(const int& SrcNId, const int& DstNId) const {
00149   TInt Dist;
00150   if (SrcNId!=StartNId) { return -1; }
00151   if (! NIdDistH.IsKeyGetDat(DstNId, Dist)) { return -1; }
00152   return Dist.Val;
00153 }
00154 
00155 template<class PGraph>
00156 int TBreathFS<PGraph>::GetRndPath(const int& SrcNId, const int& DstNId, TIntV& PathNIdV) const {
00157   PathNIdV.Clr(false);
00158   if (SrcNId!=StartNId || ! NIdDistH.IsKey(DstNId)) { return -1; }
00159   PathNIdV.Add(DstNId);
00160   TIntV CloserNIdV;
00161   int CurNId = DstNId;
00162   TInt CurDist, NextDist;
00163   while (CurNId != SrcNId) {
00164     typename PGraph::TObj::TNodeI NI = Graph->GetNI(CurNId);
00165     IAssert(NIdDistH.IsKeyGetDat(CurNId, CurDist));
00166     CloserNIdV.Clr(false);
00167     for (int e = 0; e < NI.GetDeg(); e++) {
00168       const int Next = NI.GetNbrNId(e);
00169       if (NIdDistH.IsKeyGetDat(Next, NextDist)) {
00170         if (NextDist == CurDist-1) { CloserNIdV.Add(Next); }
00171       }
00172     }
00173     IAssert(! CloserNIdV.Empty());
00174     CurNId = CloserNIdV[TInt::Rnd.GetUniDevInt(CloserNIdV.Len())];
00175     PathNIdV.Add(CurNId);
00176   }
00177   PathNIdV.Reverse();
00178   return PathNIdV.Len()-1;
00179 }
00180 
00182 // Implementation
00183 namespace TSnap {
00184 
00185 template <class PGraph>
00186 PNGraph GetBfsTree(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn) {
00187   TBreathFS<PGraph> BFS(Graph, false);
00188   BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
00189   PNGraph Tree = TNGraph::New();
00190   BFS.NIdDistH.SortByDat();
00191   for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
00192     const int NId = BFS.NIdDistH.GetKey(i);
00193     const int Dist = BFS.NIdDistH[i];
00194     typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
00195     if (!Tree->IsNode(NId)) {
00196       Tree->AddNode(NId);
00197     }
00198     if (FollowOut) {
00199       for (int e = 0; e < NI.GetInDeg(); e++) {
00200         const int Prev = NI.GetInNId(e);
00201         if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
00202           Tree->AddEdge(Prev, NId); }
00203       }
00204     }
00205     if (FollowIn) {
00206       for (int e = 0; e < NI.GetOutDeg(); e++) {
00207         const int Prev = NI.GetOutNId(e);
00208         if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
00209           Tree->AddEdge(Prev, NId); }
00210       }
00211     }
00212   }
00213   return Tree;
00214 }
00215 
00216 template <class PGraph>
00217 int GetSubTreeSz(const PGraph& Graph, const int& StartNId, const bool& FollowOut, const bool& FollowIn, int& TreeSz, int& TreeDepth) {
00218   TBreathFS<PGraph> BFS(Graph);
00219   BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
00220   TreeSz = BFS.NIdDistH.Len();
00221   TreeDepth = 0;
00222   for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
00223     TreeDepth = TMath::Mx(TreeDepth, BFS.NIdDistH[i].Val);
00224   }
00225   return TreeSz;
00226 }
00227 
00228 template <class PGraph>
00229 int GetNodesAtHop(const PGraph& Graph, const int& StartNId, const int& Hop, TIntV& NIdV, const bool& IsDir) {
00230   TBreathFS<PGraph> BFS(Graph);
00231   BFS.DoBfs(StartNId, true, !IsDir, -1, Hop);
00232   NIdV.Clr(false);
00233   for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
00234     if (BFS.NIdDistH[i] == Hop) {
00235       NIdV.Add(BFS.NIdDistH.GetKey(i)); }
00236   }
00237   return NIdV.Len();
00238 }
00239 
00240 template <class PGraph>
00241 int GetNodesAtHops(const PGraph& Graph, const int& StartNId, TIntPrV& HopCntV, const bool& IsDir) {
00242   TBreathFS<PGraph> BFS(Graph);
00243   BFS.DoBfs(StartNId, true, !IsDir, -1, TInt::Mx);
00244   TIntH HopCntH;
00245   for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
00246     HopCntH.AddDat(BFS.NIdDistH[i]) += 1;
00247   }
00248   HopCntH.GetKeyDatPrV(HopCntV);
00249   HopCntV.Sort();
00250   return HopCntV.Len();
00251 }
00252 
00253 template <class PGraph>
00254 int GetShortPath(const PGraph& Graph, const int& SrcNId, TIntH& NIdToDistH, const bool& IsDir, const int& MaxDist) {
00255   TBreathFS<PGraph> BFS(Graph);
00256   BFS.DoBfs(SrcNId, true, ! IsDir, -1, MaxDist);
00257   NIdToDistH.Clr();
00258   NIdToDistH.Swap(BFS.NIdDistH);
00259   return NIdToDistH[NIdToDistH.Len()-1];
00260 }
00261 
00262 template <class PGraph> 
00263 int GetShortPath(const PGraph& Graph, const int& SrcNId, const int& DstNId, const bool& IsDir) {
00264   TBreathFS<PGraph> BFS(Graph);
00265   BFS.DoBfs(SrcNId, true, ! IsDir, DstNId, TInt::Mx);
00266   return BFS.GetHops(SrcNId, DstNId);
00267 }
00268 
00269 template <class PGraph>
00270 int GetBfsFullDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
00271   int FullDiam;
00272   double EffDiam;
00273   GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
00274   return FullDiam;
00275 }
00276 
00277 template <class PGraph>
00278 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir) {
00279   int FullDiam;
00280   double EffDiam;
00281   GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
00282   return EffDiam;
00283 }
00284 
00285 template <class PGraph>
00286 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam) {
00287   double AvgDiam;
00288   EffDiam = -1;  FullDiam = -1;
00289   return GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam, AvgDiam);
00290 }
00291 
00292 template <class PGraph>
00293 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam, double& AvgSPL) {
00294   EffDiam = -1;  FullDiam = -1;  AvgSPL = -1;
00295   TIntFltH DistToCntH;
00296   TBreathFS<PGraph> BFS(Graph);
00297   // shotest paths
00298   TIntV NodeIdV;
00299   Graph->GetNIdV(NodeIdV);  NodeIdV.Shuffle(TInt::Rnd);
00300   for (int tries = 0; tries < TMath::Mn(NTestNodes, Graph->GetNodes()); tries++) {
00301     const int NId = NodeIdV[tries];
00302     BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
00303     for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
00304       DistToCntH.AddDat(BFS.NIdDistH[i]) += 1; }
00305   }
00306   TIntFltKdV DistNbrsPdfV;
00307   double SumPathL=0, PathCnt=0;
00308   for (int i = 0; i < DistToCntH.Len(); i++) {
00309     DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
00310     SumPathL += DistToCntH.GetKey(i) * DistToCntH[i];
00311     PathCnt += DistToCntH[i];
00312   }
00313   DistNbrsPdfV.Sort();
00314   EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
00315   FullDiam = DistNbrsPdfV.Last().Key;                // approximate full diameter (max shortest path length over the sampled nodes)
00316   AvgSPL = SumPathL/PathCnt;                        // average shortest path length
00317   return EffDiam;
00318 }
00319 
00320 template <class PGraph>
00321 double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const TIntV& SubGraphNIdV, const bool& IsDir, double& EffDiam, int& FullDiam) {
00322   EffDiam = -1;
00323   FullDiam = -1;
00324 
00325   TIntFltH DistToCntH;
00326   TBreathFS<PGraph> BFS(Graph);
00327   // shotest paths
00328   TIntV NodeIdV(SubGraphNIdV);  NodeIdV.Shuffle(TInt::Rnd);
00329   TInt Dist;
00330   for (int tries = 0; tries < TMath::Mn(NTestNodes, SubGraphNIdV.Len()); tries++) {
00331     const int NId = NodeIdV[tries];
00332     BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
00333     for (int i = 0; i < SubGraphNIdV.Len(); i++) {
00334       if (BFS.NIdDistH.IsKeyGetDat(SubGraphNIdV[i], Dist)) {
00335         DistToCntH.AddDat(Dist) += 1;
00336       }
00337     }
00338   }
00339   TIntFltKdV DistNbrsPdfV;
00340   for (int i = 0; i < DistToCntH.Len(); i++) {
00341     DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
00342   }
00343   DistNbrsPdfV.Sort();
00344   EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9);  // effective diameter (90-th percentile)
00345   FullDiam = DistNbrsPdfV.Last().Key;                 // approximate full diameter (max shortest path length over the sampled nodes)
00346   return EffDiam;                                     // average shortest path length
00347 }
00348 
00349 } // namespace TSnap