SNAP Library 4.1, Developer Reference  2018-07-26 16:30:42
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
TArtPointVisitor Class Reference

Articulation point Depth-First-Search visitor class. More...

#include <cncom.h>

Collaboration diagram for TArtPointVisitor:
Collaboration graph
[legend]

Public Member Functions

 TArtPointVisitor ()
 
 TArtPointVisitor (const int &Nodes)
 
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)
 

Public Attributes

THash< TInt, TIntPr > VnLowH
 
THash< TInt, TInt > ParentH
 
TIntSet ArtSet
 
TInt Time
 

Detailed Description

Articulation point Depth-First-Search visitor class.

Definition at line 169 of file cncom.h.

Constructor & Destructor Documentation

TArtPointVisitor::TArtPointVisitor ( )
inline

Definition at line 176 of file cncom.h.

176 { }
TArtPointVisitor::TArtPointVisitor ( const int &  Nodes)
inline

Definition at line 177 of file cncom.h.

177 : VnLowH(Nodes), ParentH(Nodes) { }
TArtPointVisitor::VnLowH
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:171
TArtPointVisitor::ParentH
THash< TInt, TInt > ParentH
Definition: cncom.h:172

Member Function Documentation

void TArtPointVisitor::BackEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 186 of file cncom.h.

References THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::IsKey(), TMath::Mn(), ParentH, TPair< TVal1, TVal2 >::Val1, TPair< TVal1, TVal2 >::Val2, and VnLowH.

186  {
187  if (ParentH.IsKey(NId1) && ParentH.GetDat(NId1)!=NId2) {
188  VnLowH.GetDat(NId1).Val2 = TMath::Mn(VnLowH.GetDat(NId1).Val2, VnLowH.GetDat(NId2).Val1); } }
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TArtPointVisitor::VnLowH
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:171
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TArtPointVisitor::ParentH
THash< TInt, TInt > ParentH
Definition: cncom.h:172

Here is the call graph for this function:

void TArtPointVisitor::DiscoverNode ( int  NId)
inline

Definition at line 178 of file cncom.h.

References THash< TKey, TDat, THashFunc >::AddDat(), Time, and VnLowH.

178 { Time++; VnLowH.AddDat(NId, TIntPr(Time, Time)); }
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TArtPointVisitor::VnLowH
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:171
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

void TArtPointVisitor::ExamineEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 184 of file cncom.h.

184 { }
void TArtPointVisitor::FinishNode ( const int &  NId)
inline

Definition at line 179 of file cncom.h.

References THashSet< TKey, THashFunc >::AddKey(), ArtSet, THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::IsKey(), TMath::Mn(), ParentH, TPair< TVal1, TVal2 >::Val1, TPair< TVal1, TVal2 >::Val2, and VnLowH.

179  {
180  if (! ParentH.IsKey(NId)) { return; } const int Prn = ParentH.GetDat(NId);
181  VnLowH.GetDat(Prn).Val2 = TMath::Mn(VnLowH.GetDat(Prn).Val2, VnLowH.GetDat(NId).Val2);
182  if (VnLowH.GetDat(Prn).Val1==1 && VnLowH.GetDat(NId).Val1!=2) { ArtSet.AddKey(Prn); }
183  if (VnLowH.GetDat(Prn).Val1!=1 && VnLowH.GetDat(NId).Val2>=VnLowH.GetDat(Prn).Val1) { ArtSet.AddKey(Prn); } }
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TArtPointVisitor::ArtSet
TIntSet ArtSet
Definition: cncom.h:173
TArtPointVisitor::VnLowH
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:171
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TArtPointVisitor::ParentH
THash< TInt, TInt > ParentH
Definition: cncom.h:172

Here is the call graph for this function:

void TArtPointVisitor::FwdEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 189 of file cncom.h.

References THash< TKey, TDat, THashFunc >::GetDat(), TMath::Mn(), TPair< TVal1, TVal2 >::Val1, TPair< TVal1, TVal2 >::Val2, and VnLowH.

189  {
190  VnLowH.GetDat(NId1).Val2 = TMath::Mn(VnLowH.GetDat(NId1).Val2, VnLowH.GetDat(NId2).Val1); }
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TArtPointVisitor::VnLowH
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:171
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35

Here is the call graph for this function:

void TArtPointVisitor::TreeEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 185 of file cncom.h.

References THash< TKey, TDat, THashFunc >::AddDat(), and ParentH.

185 { ParentH.AddDat(NId2, NId1); }
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TArtPointVisitor::ParentH
THash< TInt, TInt > ParentH
Definition: cncom.h:172

Here is the call graph for this function:

Member Data Documentation

TIntSet TArtPointVisitor::ArtSet

Definition at line 173 of file cncom.h.

Referenced by FinishNode().

THash<TInt, TInt> TArtPointVisitor::ParentH

Definition at line 172 of file cncom.h.

Referenced by BackEdge(), FinishNode(), and TreeEdge().

TInt TArtPointVisitor::Time

Definition at line 174 of file cncom.h.

Referenced by DiscoverNode().

THash<TInt, TIntPr> TArtPointVisitor::VnLowH

Definition at line 171 of file cncom.h.

Referenced by BackEdge(), DiscoverNode(), FinishNode(), and FwdEdge().

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