SNAP Library , Developer Reference  2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
TSccVisitor< PGraph, OnlyCount > Class Template Reference

#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, TIntPrTmRtH
TSStack< TIntStack
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 217 of file cncom.h.


Constructor & Destructor Documentation

template<class PGraph, bool OnlyCount = false>
TSccVisitor< PGraph, OnlyCount >::TSccVisitor ( const PGraph &  _Graph) [inline]

Definition at line 226 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 249 of file cncom.h.

{ }
template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::DiscoverNode ( int  NId) [inline]

Definition at line 228 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 247 of file cncom.h.

{ }
template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::FinishNode ( const int &  NId) [inline]

Definition at line 231 of file cncom.h.

References TCnCom::Add(), TVec< TVal >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::GetDat(), TSccVisitor< PGraph, OnlyCount >::GetMinDiscTm(), TSccVisitor< PGraph, OnlyCount >::Graph, TVec< TVal >::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 250 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 251 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 248 of file cncom.h.

{ }

Member Data Documentation

template<class PGraph, bool OnlyCount = false>
TCnComV TSccVisitor< PGraph, OnlyCount >::CnComV

Definition at line 224 of file cncom.h.

Referenced by TSnap::GetSccs().

template<class PGraph, bool OnlyCount = false>
PGraph TSccVisitor< PGraph, OnlyCount >::Graph

Definition at line 219 of file cncom.h.

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

template<class PGraph, bool OnlyCount = false>
TIntH TSccVisitor< PGraph, OnlyCount >::SccCntH

Definition at line 223 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
template<class PGraph, bool OnlyCount = false>
TInt TSccVisitor< PGraph, OnlyCount >::Time

Definition at line 222 of file cncom.h.

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

template<class PGraph, bool OnlyCount = false>
THash<TInt, TIntPr> TSccVisitor< PGraph, OnlyCount >::TmRtH

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