SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
TSccVisitor< PGraph, OnlyCount > Class Template Reference

Strongly connected componetns Depht-First-Search visitor class. More...

#include <cncom.h>

Collaboration diagram for TSccVisitor< PGraph, OnlyCount >:
Collaboration graph
[legend]

Public Member Functions

 TSccVisitor (const PGraph &_Graph)
 
void DiscoverNode (int NId)
 
void FinishNode (const int &NId)
 
void ExamineEdge (const int &NId1, const int &NId2)
 
void TreeEdge (const int &NId1, const int &NId2)
 
void BackEdge (const int &NId1, const int &NId2)
 
void FwdEdge (const int &NId1, const int &NId2)
 
int GetMinDiscTm (const int &NId1, const int &NId2) const
 

Public Attributes

PGraph Graph
 
THash< TInt, TIntPr > TmRtH
 
TSStack< TInt > Stack
 
TInt Time
 
TIntH SccCntH
 
TCnComV CnComV
 

Detailed Description

template<class PGraph, bool OnlyCount = false>
class TSccVisitor< PGraph, OnlyCount >

Strongly connected componetns Depht-First-Search visitor class.

Definition at line 234 of file cncom.h.

Constructor & Destructor Documentation

template<class PGraph, bool OnlyCount = false>
TSccVisitor< PGraph, OnlyCount >::TSccVisitor ( const PGraph &  _Graph)
inline

Definition at line 243 of file cncom.h.

243  :
244  Graph(_Graph), TmRtH(Graph->GetNodes()), Stack(Graph->GetNodes()) { }
TSccVisitor::Stack
TSStack< TInt > Stack
Definition: cncom.h:238
TSccVisitor::Graph
PGraph Graph
Definition: cncom.h:236
TSccVisitor::TmRtH
THash< TInt, TIntPr > TmRtH
Definition: cncom.h:237

Member Function Documentation

template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::BackEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 266 of file cncom.h.

266 { }
template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::DiscoverNode ( int  NId)
inline

Definition at line 245 of file cncom.h.

References THash< TKey, TDat, THashFunc >::AddDat(), TSStack< TVal >::Push(), TSccVisitor< PGraph, OnlyCount >::Stack, TSccVisitor< PGraph, OnlyCount >::Time, and TSccVisitor< PGraph, OnlyCount >::TmRtH.

245  {
246  Time++; TmRtH.AddDat(NId, TIntPr(-Time, NId)); // negative time -- node not yet in any SCC
247  Stack.Push(NId); }
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSccVisitor::Stack
TSStack< TInt > Stack
Definition: cncom.h:238
TSStack::Push
void Push()
Definition: ds.h:2596
TSccVisitor::Time
TInt Time
Definition: cncom.h:239
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TSccVisitor::TmRtH
THash< TInt, TIntPr > TmRtH
Definition: cncom.h:237

Here is the call graph for this function:

template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::ExamineEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 264 of file cncom.h.

264 { }
template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::FinishNode ( const int &  NId)
inline

Definition at line 248 of file cncom.h.

References TCnCom::Add(), TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::GetDat(), TSccVisitor< PGraph, OnlyCount >::GetMinDiscTm(), TSccVisitor< PGraph, OnlyCount >::Graph, TVec< TVal, TSizeTy >::Last(), TSStack< TVal >::Pop(), TSccVisitor< PGraph, OnlyCount >::SccCntH, TSccVisitor< PGraph, OnlyCount >::Stack, TSccVisitor< PGraph, OnlyCount >::TmRtH, TSStack< TVal >::Top(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

248  {
249  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
250  TIntPr& TmRtN = TmRtH.GetDat(NId);
251  int W = -1, Cnt = 0;
252  for (int i = 0; i < NI.GetOutDeg(); i++) {
253  W = NI.GetOutNId(i);
254  const TIntPr& TmRtW = TmRtH.GetDat(W);
255  if (TmRtW.Val1 < 0) { // node not yet in any SCC
256  TmRtN.Val2 = GetMinDiscTm(TmRtN.Val2, TmRtW.Val2); } }
257  if (TmRtN.Val2 == NId) {
258  if (! OnlyCount) { CnComV.Add(); }
259  do { W = Stack.Top(); Stack.Pop();
260  if (OnlyCount) { Cnt++; } else { CnComV.Last().Add(W); }
261  TmRtH.GetDat(W).Val1 = abs(TmRtH.GetDat(W).Val1); // node is in SCC
262  } while (W != NId);
263  if (OnlyCount) { SccCntH.AddDat(Cnt) += 1; } } }
TCnCom::Add
void Add(const int &NodeId)
Definition: cncom.h:104
TSStack::Top
TVal & Top()
Definition: ds.h:2594
TSccVisitor::CnComV
TCnComV CnComV
Definition: cncom.h:241
TSccVisitor::GetMinDiscTm
int GetMinDiscTm(const int &NId1, const int &NId2) const
Definition: cncom.h:268
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TSccVisitor::Stack
TSStack< TInt > Stack
Definition: cncom.h:238
TSccVisitor::SccCntH
TIntH SccCntH
Definition: cncom.h:240
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TPair
Definition: ds.h:32
TSccVisitor::Graph
PGraph Graph
Definition: cncom.h:236
TSStack::Pop
void Pop()
Definition: ds.h:2598
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TSccVisitor::TmRtH
THash< TInt, TIntPr > TmRtH
Definition: cncom.h:237

Here is the call graph for this function:

template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::FwdEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 267 of file cncom.h.

267 { }
template<class PGraph, bool OnlyCount = false>
int TSccVisitor< PGraph, OnlyCount >::GetMinDiscTm ( const int &  NId1,
const int &  NId2 
) const
inline

Definition at line 268 of file cncom.h.

References THash< TKey, TDat, THashFunc >::GetDat(), TSccVisitor< PGraph, OnlyCount >::TmRtH, and TPair< TVal1, TVal2 >::Val1.

Referenced by TSccVisitor< PGraph, OnlyCount >::FinishNode().

268  {
269  return abs(TmRtH.GetDat(NId1).Val1) < abs(TmRtH.GetDat(NId2).Val1) ? NId1 : NId2; }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TSccVisitor::TmRtH
THash< TInt, TIntPr > TmRtH
Definition: cncom.h:237

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::TreeEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 265 of file cncom.h.

265 { }

Member Data Documentation

template<class PGraph, bool OnlyCount = false>
TCnComV TSccVisitor< PGraph, OnlyCount >::CnComV

Definition at line 241 of file cncom.h.

Referenced by TSnap::GetSccs().

template<class PGraph, bool OnlyCount = false>
PGraph TSccVisitor< PGraph, OnlyCount >::Graph

Definition at line 236 of file cncom.h.

Referenced by TSccVisitor< PGraph, OnlyCount >::FinishNode().

template<class PGraph, bool OnlyCount = false>
TIntH TSccVisitor< PGraph, OnlyCount >::SccCntH

Definition at line 240 of file cncom.h.

Referenced by TSccVisitor< PGraph, OnlyCount >::FinishNode(), and TSnap::GetSccSzCnt().

template<class PGraph, bool OnlyCount = false>
TSStack<TInt> TSccVisitor< PGraph, OnlyCount >::Stack

Definition at line 238 of file cncom.h.

Referenced by TSccVisitor< PGraph, OnlyCount >::DiscoverNode(), and TSccVisitor< PGraph, OnlyCount >::FinishNode().

template<class PGraph, bool OnlyCount = false>
TInt TSccVisitor< PGraph, OnlyCount >::Time

Definition at line 239 of file cncom.h.

Referenced by TSccVisitor< PGraph, OnlyCount >::DiscoverNode().

template<class PGraph, bool OnlyCount = false>
THash<TInt, TIntPr> TSccVisitor< PGraph, OnlyCount >::TmRtH

Definition at line 237 of file cncom.h.

Referenced by TSccVisitor< PGraph, OnlyCount >::DiscoverNode(), TSccVisitor< PGraph, OnlyCount >::FinishNode(), and TSccVisitor< PGraph, OnlyCount >::GetMinDiscTm().

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