#include <cncom.h>

Collaboration diagram for TCnCom:

Public Member Functions
	TCnCom ()

	TCnCom (const TIntV &NodeIdV)

	TCnCom (const TCnCom &CC)

	TCnCom (TSIn &SIn)

void	Save (TSOut &SOut) const

TCnCom &	operator= (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 TInt &	operator[] (const int &NIdN) const

const TIntV &	operator() () const

TIntV &	operator() ()

const TInt &	GetVal (const int &NIdN) const

void	Sort (const bool &Asc=true)

bool	IsNIdIn (const int &NId) const

const TInt &	GetRndNId () const

int	GetPrimHashCd () const

int	GetSecHashCd () 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.

92 : NIdV() { }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TCnCom::TCnCom ( const TIntV & NodeIdV )

inline

Definition at line 93 of file cncom.h.

93 : NIdV(NodeIdV) { }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TCnCom::TCnCom ( const TCnCom & CC )

inline

Definition at line 94 of file cncom.h.

94 : NIdV(CC.NIdV) { }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TCnCom::TCnCom ( TSIn & SIn )

inline

Definition at line 95 of file cncom.h.

95 : NIdV(SIn) { }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

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(), TSnap::Infomap(), and TSnap::InfomapOnline().

104 { NIdV.Add(NodeId); }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TVec::Add

TSizeTy Add()

Adds a new element at the end of the vector, after its current last element.

Definition: ds.h:559

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.

103 { NIdV.Clr(); }

TVec::Clr

void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)

Clears the contents of the vector.

Definition: ds.h:953

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

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.

102 { return NIdV.Empty(); }

TVec::Empty

bool Empty() const

Tests whether the vector is empty.

Definition: ds.h:530

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

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 124 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:

int TCnCom::GetPrimHashCd ( ) const

inline

Definition at line 119 of file cncom.h.

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

119 { return NIdV.GetPrimHashCd(); }

TVec::GetPrimHashCd

int GetPrimHashCd() const

Returns primary hash code of the vector. Used by THash.

Definition: ds.h:930

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

Here is the call graph for this function:

const TInt& TCnCom::GetRndNId ( ) const

inline

Definition at line 111 of file cncom.h.

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

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

TInt::Rnd

static TRnd Rnd

Definition: dt.h:1051

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TCnCom::Len

int Len() const

Definition: cncom.h:101

TRnd::GetUniDevInt

int GetUniDevInt(const int &Range=0)

Definition: dt.cpp:39

Here is the call graph for this function:

int TCnCom::GetSecHashCd ( ) const

inline

Definition at line 120 of file cncom.h.

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

120 { return NIdV.GetSecHashCd(); }

TVec::GetSecHashCd

int GetSecHashCd() const

Returns secondary hash code of the vector. Used by THash.

Definition: ds.h:942

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

Here is the call graph for this function:

const TInt& TCnCom::GetVal ( const int & NIdN ) const

inline

Definition at line 108 of file cncom.h.

References operator[]().

108 { return operator[](NIdN); }

TCnCom::operator[]

const TInt & operator[](const int &NIdN) const

Definition: cncom.h:105

Here is the call graph for this function:

bool TCnCom::IsNIdIn ( const int & NId ) const

inline

Definition at line 110 of file cncom.h.

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

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

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TVec::SearchBin

TSizeTy SearchBin(const TVal &Val) const

Returns the position of an element with value Val.

Definition: ds.h:1418

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().

101 { return NIdV.Len(); }

TVec::Len

TSizeTy Len() const

Returns the number of elements in the vector.

Definition: ds.h:535

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

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.

106 { return NIdV; }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TIntV& TCnCom::operator() ( )

inline

Definition at line 107 of file cncom.h.

References NIdV.

107 { return NIdV; }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

bool TCnCom::operator< ( const TCnCom & CC ) const

inline

Definition at line 99 of file cncom.h.

References NIdV.

99 { return NIdV < CC.NIdV; }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

TCnCom& TCnCom::operator= ( const TCnCom & CC )

inline

Definition at line 97 of file cncom.h.

References NIdV.

97 { if (this != &CC) NIdV = CC.NIdV; return *this; }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

bool TCnCom::operator== ( const TCnCom & CC ) const

inline

Definition at line 98 of file cncom.h.

References NIdV.

98 { return NIdV == CC.NIdV; }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

const TInt& TCnCom::operator[] ( const int & NIdN ) const

inline

Definition at line 105 of file cncom.h.

References NIdV.

Referenced by GetVal().

105 { return NIdV[NIdN]; }

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

Here is the caller graph for this function:

void TCnCom::Save ( TSOut & SOut ) const

inline

Definition at line 96 of file cncom.h.

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

96 { NIdV.Save(SOut); }

TVec::Save

void Save(TSOut &SOut) const

Definition: ds.h:885

TCnCom::NIdV

TIntV NIdV

Definition: cncom.h:90

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);
 }