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
TBiConVisitor Class Reference

Biconnected componetns Depth-First-Search visitor class. More...

#include <cncom.h>

Collaboration diagram for TBiConVisitor:

Public Member Functions

 TBiConVisitor ()
 
 TBiConVisitor (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, TIntPrVnLowH
 
THash< TInt, TIntParentH
 
TSStack< TIntPrStack
 
TCnComV CnComV
 
TIntSet NSet
 
TInt Time
 

Detailed Description

Biconnected componetns Depth-First-Search visitor class.

Definition at line 195 of file cncom.h.

Constructor & Destructor Documentation

TBiConVisitor::TBiConVisitor ( )
inline

Definition at line 204 of file cncom.h.

204 { }
TBiConVisitor::TBiConVisitor ( const int &  Nodes)
inline

Definition at line 205 of file cncom.h.

205 : VnLowH(Nodes), ParentH(Nodes), Stack(Nodes) { }
THash< TInt, TInt > ParentH
Definition: cncom.h:198
TSStack< TIntPr > Stack
Definition: cncom.h:199
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:197

Member Function Documentation

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

Definition at line 224 of file cncom.h.

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

224  {
225  if (ParentH.IsKey(NId1) && ParentH.GetDat(NId1)!=NId2) {
226  Stack.Push(TIntPr(NId1, NId2));
227  VnLowH.GetDat(NId1).Val2 = TMath::Mn(VnLowH.GetDat(NId1).Val2, VnLowH.GetDat(NId2).Val1); } }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
THash< TInt, TInt > ParentH
Definition: cncom.h:198
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TSStack< TIntPr > Stack
Definition: cncom.h:199
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:197
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
bool IsKey(const TKey &Key) const
Definition: hash.h:258

Here is the call graph for this function:

void TBiConVisitor::DiscoverNode ( int  NId)
inline

Definition at line 206 of file cncom.h.

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

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

Here is the call graph for this function:

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

Definition at line 220 of file cncom.h.

220 { }
void TBiConVisitor::FinishNode ( const int &  NId)
inline

Definition at line 207 of file cncom.h.

References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::Clr(), THash< TKey, TDat, THashFunc >::GetDat(), THashSet< TKey, THashFunc >::GetKeyV(), THash< TKey, TDat, THashFunc >::IsKey(), TMath::Mn(), NSet, ParentH, TVec< TVal, TSizeTy >::Sort(), Stack, TPair< TVal1, TVal2 >::Val1, TPair< TVal1, TVal2 >::Val2, and VnLowH.

207  {
208  if (! ParentH.IsKey(NId)) { return; } const int Prn = ParentH.GetDat(NId);
210  if (VnLowH.GetDat(NId).Val2 >= VnLowH.GetDat(Prn).Val1) {
211  NSet.Clr(false);
212  while (! Stack.Empty() && Stack.Top() != TIntPr(Prn, NId)) {
213  const TIntPr& Top = Stack.Top();
214  NSet.AddKey(Top.Val1); NSet.AddKey(Top.Val2); Stack.Pop(); }
215  if (! Stack.Empty()) {
216  const TIntPr& Top = Stack.Top();
217  NSet.AddKey(Top.Val1); NSet.AddKey(Top.Val2); Stack.Pop(); }
218  TIntV NIdV; NSet.GetKeyV(NIdV); NIdV.Sort();
219  CnComV.Add(NIdV); } }
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:1347
THash< TInt, TInt > ParentH
Definition: cncom.h:198
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TCnComV CnComV
Definition: cncom.h:200
TIntSet NSet
Definition: cncom.h:201
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
int AddKey(const TKey &Key)
Definition: shash.h:1254
TSStack< TIntPr > Stack
Definition: cncom.h:199
Definition: ds.h:32
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:197
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

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

Definition at line 228 of file cncom.h.

228 { }
void TBiConVisitor::TreeEdge ( const int &  NId1,
const int &  NId2 
)
inline

Definition at line 221 of file cncom.h.

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

221  {
222  ParentH.AddDat(NId2, NId1);
223  Stack.Push(TIntPr(NId1, NId2)); }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
THash< TInt, TInt > ParentH
Definition: cncom.h:198
TSStack< TIntPr > Stack
Definition: cncom.h:199
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

Member Data Documentation

TCnComV TBiConVisitor::CnComV

Definition at line 200 of file cncom.h.

TIntSet TBiConVisitor::NSet

Definition at line 201 of file cncom.h.

Referenced by FinishNode().

THash<TInt, TInt> TBiConVisitor::ParentH

Definition at line 198 of file cncom.h.

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

TSStack<TIntPr> TBiConVisitor::Stack

Definition at line 199 of file cncom.h.

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

TInt TBiConVisitor::Time

Definition at line 202 of file cncom.h.

Referenced by DiscoverNode().

THash<TInt, TIntPr> TBiConVisitor::VnLowH

Definition at line 197 of file cncom.h.

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


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