SNAP Library 2.1, Developer 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
TCnCom Class Reference

#include <cncom.h>

Collaboration diagram for TCnCom:

List of all members.

Public Member Functions

 TCnCom ()
 TCnCom (const TIntV &NodeIdV)
 TCnCom (const TCnCom &CC)
 TCnCom (TSIn &SIn)
void Save (TSOut &SOut) const
TCnComoperator= (const TCnCom &CC)
bool operator== (const TCnCom &CC) const
bool operator< (const TCnCom &CC) const
int Len () const
bool Empty () const
void Clr ()
void Add (const int &NodeId)
const TIntoperator[] (const int &NIdN) const
const TIntVoperator() () const
TIntVoperator() ()
void Sort (const bool &Asc=true)
bool IsNIdIn (const int &NId) const
const TIntGetRndNId () const

Static Public Member Functions

static void Dump (const TCnComV &CnComV, const TStr &Desc=TStr())
static void SaveTxt (const TCnComV &CnComV, const TStr &FNm, const TStr &Desc=TStr())
template<class PGraph , class TVisitor >
static void GetDfsVisitor (const PGraph &Graph, TVisitor &Visitor)

Public Attributes

TIntV NIdV

Detailed Description

Connected Component. Connected component is defined by a vector of its node IDs.

Definition at line 88 of file cncom.h.


Constructor & Destructor Documentation

TCnCom::TCnCom ( ) [inline]

Definition at line 92 of file cncom.h.

: NIdV() { }
TCnCom::TCnCom ( const TIntV NodeIdV) [inline]

Definition at line 93 of file cncom.h.

: NIdV(NodeIdV) { }
TCnCom::TCnCom ( const TCnCom CC) [inline]

Definition at line 94 of file cncom.h.

: NIdV(CC.NIdV) { }
TCnCom::TCnCom ( TSIn SIn) [inline]

Definition at line 95 of file cncom.h.

: NIdV(SIn) { }

Member Function Documentation

void TCnCom::Add ( const int &  NodeId) [inline]

Definition at line 104 of file cncom.h.

References TVec< TVal, TSizeTy >::Add(), and NIdV.

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

{ NIdV.Add(NodeId); }

Here is the call graph for this function:

Here is the caller graph for this function:

void TCnCom::Clr ( ) [inline]

Definition at line 103 of file cncom.h.

References TVec< TVal, TSizeTy >::Clr(), and NIdV.

{ NIdV.Clr(); }

Here is the call graph for this function:

void TCnCom::Dump ( const TCnComV CnComV,
const TStr Desc = TStr() 
) [static]

Definition at line 3 of file cncom.cpp.

References TStr::CStr(), TStr::Empty(), TVec< TVal, TSizeTy >::Len(), and NIdV.

                                                         {
  if (! Desc.Empty()) { printf("%s:\n", Desc.CStr()); }
  for (int cc = 0; cc < CnComV.Len(); cc++) {
    const TIntV& NIdV = CnComV[cc].NIdV;
    printf("%d : ", NIdV.Len());
    for (int i = 0; i < NIdV.Len(); i++) { printf(" %d", NIdV[i].Val); }
    printf("\n");
  }
}

Here is the call graph for this function:

bool TCnCom::Empty ( ) const [inline]

Definition at line 102 of file cncom.h.

References TVec< TVal, TSizeTy >::Empty(), and NIdV.

{ return NIdV.Empty(); }

Here is the call graph for this function:

template<class PGraph , class TVisitor >
void TCnCom::GetDfsVisitor ( const PGraph &  Graph,
TVisitor &  Visitor 
) [static]

Depth-First-Search. Depending on the stage of DFS a different member function of Visitor class is called. See source code for details.

Definition at line 121 of file cncom.h.

References THash< TKey, TDat, THashFunc >::AddDat(), TSStack< TVal >::Empty(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::IsKey(), TSStack< TVal >::Pop(), TSStack< TVal >::Push(), TSStack< TVal >::Top(), TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.

Referenced by TSnap::GetArtPoints(), TSnap::GetBiCon(), TSnap::GetSccs(), and TSnap::GetSccSzCnt().

                                                                 {
  const int Nodes = Graph->GetNodes();
  TSStack<TIntTr> Stack(Nodes);
  int edge=0, Deg=0, U=0;
  TIntH ColorH(Nodes);
  typename PGraph::TObj::TNodeI NI, UI;
  for (NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    U = NI.GetId();
    if (! ColorH.IsKey(U)) {         // is unvisited node
      ColorH.AddDat(U, 1); 
      Visitor.DiscoverNode(U);       // discover
      Stack.Push(TIntTr(U, 0, Graph->GetNI(U).GetOutDeg()));
      while (! Stack.Empty()) {
        const TIntTr& Top = Stack.Top();
        U=Top.Val1; edge=Top.Val2; Deg=Top.Val3;
        typename PGraph::TObj::TNodeI UI = Graph->GetNI(U);
        Stack.Pop();
        while (edge != Deg) {
          const int V = UI.GetOutNId(edge);
          Visitor.ExamineEdge(U, V); // examine edge
          if (! ColorH.IsKey(V)) {
            Visitor.TreeEdge(U, V);  // tree edge
            Stack.Push(TIntTr(U, ++edge, Deg));
            U = V;
            ColorH.AddDat(U, 1); 
            Visitor.DiscoverNode(U); // discover
            UI = Graph->GetNI(U);
            edge = 0;  Deg = UI.GetOutDeg();
          }
          else if (ColorH.GetDat(V) == 1) {
            Visitor.BackEdge(U, V);  // edge upward
            ++edge; }
          else {
            Visitor.FwdEdge(U, V);   // edge downward
            ++edge; }
        }
        ColorH.AddDat(U, 2); 
        Visitor.FinishNode(U);       // finish
      }
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

const TInt& TCnCom::GetRndNId ( ) const [inline]

Definition at line 110 of file cncom.h.

References TRnd::GetUniDevInt(), Len(), NIdV, and TInt::Rnd.

{ return NIdV[TInt::Rnd.GetUniDevInt(Len())]; }

Here is the call graph for this function:

bool TCnCom::IsNIdIn ( const int &  NId) const [inline]

Definition at line 109 of file cncom.h.

References NIdV, and TVec< TVal, TSizeTy >::SearchBin().

{ return NIdV.SearchBin(NId) != -1; }

Here is the call graph for this function:

int TCnCom::Len ( ) const [inline]

Definition at line 101 of file cncom.h.

References TVec< TVal, TSizeTy >::Len(), and NIdV.

Referenced by GetRndNId().

{ return NIdV.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

const TIntV& TCnCom::operator() ( ) const [inline]

Definition at line 106 of file cncom.h.

References NIdV.

{ return NIdV; }
TIntV& TCnCom::operator() ( ) [inline]

Definition at line 107 of file cncom.h.

References NIdV.

{ return NIdV; }
bool TCnCom::operator< ( const TCnCom CC) const [inline]

Definition at line 99 of file cncom.h.

References NIdV.

{ return NIdV < CC.NIdV; }
TCnCom& TCnCom::operator= ( const TCnCom CC) [inline]

Definition at line 97 of file cncom.h.

References NIdV.

{ if (this != &CC) NIdV = CC.NIdV;  return *this; }
bool TCnCom::operator== ( const TCnCom CC) const [inline]

Definition at line 98 of file cncom.h.

References NIdV.

{ return NIdV == CC.NIdV; }
const TInt& TCnCom::operator[] ( const int &  NIdN) const [inline]

Definition at line 105 of file cncom.h.

References NIdV.

{ return NIdV[NIdN]; }
void TCnCom::Save ( TSOut SOut) const [inline]

Definition at line 96 of file cncom.h.

References NIdV, and TVec< TVal, TSizeTy >::Save().

{ NIdV.Save(SOut); }

Here is the call graph for this function:

void TCnCom::SaveTxt ( const TCnComV CnComV,
const TStr FNm,
const TStr Desc = TStr() 
) [static]

Definition at line 13 of file cncom.cpp.

References TStr::CStr(), TStr::Empty(), TVec< TVal, TSizeTy >::Len(), and NIdV.

                                                                             {
  FILE *F = fopen(FNm.CStr(), "wt");
  if (! Desc.Empty()) { fprintf(F, "# %s\n", Desc.CStr()); }
  fprintf(F, "# Connected Components:\t%d\n", CnComV.Len());
  fprintf(F, "# Connected components (format: <Size>\\t<NodeId1>\\t<NodeId2>...)\n");
  for (int cc = 0; cc < CnComV.Len(); cc++) {
    const TIntV& NIdV = CnComV[cc].NIdV;
    fprintf(F, "%d", NIdV.Len());
    for (int i = 0; i < NIdV.Len(); i++) { fprintf(F, "\t%d", NIdV[i].Val); }
    fprintf(F, "\n");
  }
  fclose(F);
}

Here is the call graph for this function:

void TCnCom::Sort ( const bool &  Asc = true) [inline]

Definition at line 108 of file cncom.h.

References NIdV, and TVec< TVal, TSizeTy >::Sort().

{ NIdV.Sort(Asc); }

Here is the call graph for this function:


Member Data Documentation


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