SNAP Library 2.1, User Reference  2013-09-25 10:47:25
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
Public Member Functions | Public Attributes
TSccVisitor< PGraph, OnlyCount > Class Template Reference

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

#include <cncom.h>

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

Constructor & Destructor Documentation

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

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

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

Definition at line 242 of file cncom.h.

                             {
    Time++; TmRtH.AddDat(NId, TIntPr(-Time, NId)); // negative time -- node not yet in any SCC
    Stack.Push(NId); }
template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::ExamineEdge ( 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 >::FinishNode ( const int &  NId) [inline]

Definition at line 245 of file cncom.h.

                                  {
    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; } } }
template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::FwdEdge ( const int &  NId1,
const int &  NId2 
) [inline]

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

                                                           {
    return abs(TmRtH.GetDat(NId1).Val1) < abs(TmRtH.GetDat(NId2).Val1) ? NId1 : NId2; }
template<class PGraph, bool OnlyCount = false>
void TSccVisitor< PGraph, OnlyCount >::TreeEdge ( const int &  NId1,
const int &  NId2 
) [inline]

Definition at line 262 of file cncom.h.

{ }

Member Data Documentation

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

Definition at line 238 of file cncom.h.

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

Definition at line 233 of file cncom.h.

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

Definition at line 237 of file cncom.h.

template<class PGraph, bool OnlyCount = false>
TSStack<TInt> TSccVisitor< PGraph, OnlyCount >::Stack

Definition at line 235 of file cncom.h.

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

Definition at line 236 of file cncom.h.

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

Definition at line 234 of file cncom.h.

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