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

#include <cncom.h>

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.

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

void TArtPointVisitor::DiscoverNode ( int NId )

inline

Definition at line 178 of file cncom.h.

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

TIntPr

TPair< TInt, TInt > TIntPr

Definition: ds.h:83

TArtPointVisitor::Time

TInt Time

Definition: cncom.h:174

TArtPointVisitor::VnLowH

THash< TInt, TIntPr > VnLowH

Definition: cncom.h:171

THash::AddDat

TDat & AddDat(const TKey &Key)

Definition: hash.h:238

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.

                                   {
     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(Prn).Val1==1 && VnLowH.GetDat(NId).Val1!=2) { ArtSet.AddKey(Prn); }
     if (VnLowH.GetDat(Prn).Val1!=1 && VnLowH.GetDat(NId).Val2>=VnLowH.GetDat(Prn).Val1) { ArtSet.AddKey(Prn); } }