TSccVisitor< PGraph, OnlyCount > Class Template Reference

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

#include <cncom.h>

Collaboration diagram for TSccVisitor< PGraph, OnlyCount >:

List of all members.

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 229 of file cncom.h.

---

Constructor & Destructor Documentation

template<class PGraph, bool OnlyCount = false>

TSccVisitor< PGraph, OnlyCount >::TSccVisitor

(

const PGraph &

_Graph

)

[inline]

Definition at line 238 of file cncom.h.

                                    :
      Graph(_Graph), TmRtH(Graph->GetNodes()), Stack(Graph->GetNodes()) { }

---

Member Function Documentation

template<class PGraph, bool OnlyCount = false>

void TSccVisitor< PGraph, OnlyCount >::BackEdge	(	const int &	NId1,
		const int &	NId2
	)		[inline]

Definition at line 261 of file cncom.h.

{ }

template<class PGraph, bool OnlyCount = false>

void TSccVisitor< PGraph, OnlyCount >::DiscoverNode

(

int

NId

)

[inline]

Definition at line 240 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.

                             {
    Time++; TmRtH.AddDat(NId, TIntPr(-Time, NId)); // negative time -- node not yet in any SCC
    Stack.Push(NId); }

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 259 of file cncom.h.

{ }

template<class PGraph, bool OnlyCount = false>

void TSccVisitor< PGraph, OnlyCount >::FinishNode

(

const int &

NId

)

[inline]

Definition at line 243 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.

                                  {
    typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
    TIntPr& TmRtN = TmRtH.GetDat(NId);
    int W = -1, Cnt = 0;
    for (int i = 0; i < NI.GetOutDeg(); i++) {
      W = NI.GetOutNId(i);
      const TIntPr& TmRtW = TmRtH.GetDat(W);
      if (TmRtW.Val1 < 0) { // node not yet in any SCC
        TmRtN.Val2 = GetMinDiscTm(TmRtN.Val2, TmRtW.Val2); } }
    if (TmRtN.Val2 == NId) {
      if (! OnlyCount) { CnComV.Add(); }
      do { W = Stack.Top();  Stack.Pop();
      if (OnlyCount) { Cnt++; } else { CnComV.Last().Add(W); }
      TmRtH.GetDat(W).Val1 = abs(TmRtH.GetDat(W).Val1); // node is in SCC
      } while (W != NId);
      if (OnlyCount) { SccCntH.AddDat(Cnt) += 1; } } }

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 262 of file cncom.h.

{ }

template<class PGraph, bool OnlyCount = false>

int TSccVisitor< PGraph, OnlyCount >::GetMinDiscTm	(	const int &	NId1,
		const int &	NId2
	)		const [inline]

Definition at line 263 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().

                                                           {
    return abs(TmRtH.GetDat(NId1).Val1) < abs(TmRtH.GetDat(NId2).Val1) ? NId1 : NId2; }

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 260 of file cncom.h.

{ }

---

Member Data Documentation

template<class PGraph, bool OnlyCount = false>

TCnComV TSccVisitor< PGraph, OnlyCount >::CnComV

Definition at line 236 of file cncom.h.

Referenced by TSnap::GetSccs().

template<class PGraph, bool OnlyCount = false>

PGraph TSccVisitor< PGraph, OnlyCount >::Graph

Definition at line 231 of file cncom.h.

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

template<class PGraph, bool OnlyCount = false>

TIntH TSccVisitor< PGraph, OnlyCount >::SccCntH

Definition at line 235 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 233 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 234 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 232 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:

• snap-core/cncom.h