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, TIntPr >	VnLowH
THash< TInt, TInt >	ParentH
TSStack< TIntPr >	Stack
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.

{ }

TBiConVisitor::TBiConVisitor ( const int &  Nodes )

inline

Definition at line 205 of file cncom.h.

: VnLowH(Nodes), ParentH(Nodes), Stack(Nodes) { }

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.

                                                  {
    if (ParentH.IsKey(NId1) && ParentH.GetDat(NId1)!=NId2) {
      Stack.Push(TIntPr(NId1, NId2));
      VnLowH.GetDat(NId1).Val2 = TMath::Mn(VnLowH.GetDat(NId1).Val2, VnLowH.GetDat(NId2).Val1); } }

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.

{ Time++; VnLowH.AddDat(NId, TIntPr(Time, Time)); }

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.

{ }

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.

                                  {
    if (! ParentH.IsKey(NId)) { return; }  const int Prn = ParentH.GetDat(NId);
    VnLowH.GetDat(Prn).Val2 = TMath::Mn(VnLowH.GetDat(Prn).Val2, VnLowH.GetDat(NId).Val2);
    if (VnLowH.GetDat(NId).Val2 >= VnLowH.GetDat(Prn).Val1) {
      NSet.Clr(false);
      while (! Stack.Empty() && Stack.Top() != TIntPr(Prn, NId)) {
        const TIntPr& Top = Stack.Top();
        NSet.AddKey(Top.Val1);  NSet.AddKey(Top.Val2); Stack.Pop();  }
      if (! Stack.Empty()) {
        const TIntPr& Top = Stack.Top();
        NSet.AddKey(Top.Val1);  NSet.AddKey(Top.Val2); Stack.Pop(); }
      TIntV NIdV; NSet.GetKeyV(NIdV);  NIdV.Sort();
      CnComV.Add(NIdV); } }

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.

{ }

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.

                                                  {
    ParentH.AddDat(NId2, NId1);
    Stack.Push(TIntPr(NId1, NId2)); }

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:

• snap-core/cncom.h