SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
TCnCom Class Reference

#include <cncom.h>

Collaboration diagram for TCnCom:
Collaboration graph
[legend]

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

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

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

103 { NIdV.Clr(); }
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
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.

3  {
4  if (! Desc.Empty()) { printf("%s:\n", Desc.CStr()); }
5  for (int cc = 0; cc < CnComV.Len(); cc++) {
6  const TIntV& NIdV = CnComV[cc].NIdV;
7  printf("%d : ", NIdV.Len());
8  for (int i = 0; i < NIdV.Len(); i++) { printf(" %d", NIdV[i].Val); }
9  printf("\n");
10  }
11 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TCnCom::NIdV
TIntV NIdV
Definition: cncom.h:90
TStr::Empty
bool Empty() const
Definition: dt.h:491
TStr::CStr
char * CStr()
Definition: dt.h:479

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

102 { return NIdV.Empty(); }
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
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(), edge, 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().

124  {
125  const int Nodes = Graph->GetNodes();
126  TSStack<TIntTr> Stack(Nodes);
127  int edge=0, Deg=0, U=0;
128  TIntH ColorH(Nodes);
129  typename PGraph::TObj::TNodeI NI, UI;
130  for (NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
131  U = NI.GetId();
132  if (! ColorH.IsKey(U)) { // is unvisited node
133  ColorH.AddDat(U, 1);
134  Visitor.DiscoverNode(U); // discover
135  Stack.Push(TIntTr(U, 0, Graph->GetNI(U).GetOutDeg()));
136  while (! Stack.Empty()) {
137  const TIntTr& Top = Stack.Top();
138  U=Top.Val1; edge=Top.Val2; Deg=Top.Val3;
139  typename PGraph::TObj::TNodeI UI = Graph->GetNI(U);
140  Stack.Pop();
141  while (edge != Deg) {
142  const int V = UI.GetOutNId(edge);
143  Visitor.ExamineEdge(U, V); // examine edge
144  if (! ColorH.IsKey(V)) {
145  Visitor.TreeEdge(U, V); // tree edge
146  Stack.Push(TIntTr(U, ++edge, Deg));
147  U = V;
148  ColorH.AddDat(U, 1);
149  Visitor.DiscoverNode(U); // discover
150  UI = Graph->GetNI(U);
151  edge = 0; Deg = UI.GetOutDeg();
152  }
153  else if (ColorH.GetDat(V) == 1) {
154  Visitor.BackEdge(U, V); // edge upward
155  ++edge; }
156  else {
157  Visitor.FwdEdge(U, V); // edge downward
158  ++edge; }
159  }
160  ColorH.AddDat(U, 2);
161  Visitor.FinishNode(U); // finish
162  }
163  }
164  }
165 }
TTriple
Definition: ds.h:130
TTriple::Val1
TVal1 Val1
Definition: ds.h:132
TTriple::Val2
TVal2 Val2
Definition: ds.h:133
TSStack
Definition: ds.h:2575
TIntTr
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
TTriple::Val3
TVal3 Val3
Definition: ds.h:134

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

119 { return NIdV.GetPrimHashCd(); }
TVec::GetPrimHashCd
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:999
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(), and TInt::Rnd.

111 { return NIdV[TInt::Rnd.GetUniDevInt(Len())]; }
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1146
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().

120 { return NIdV.GetSecHashCd(); }
TVec::GetSecHashCd
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:1011
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 TVec< TVal, TSizeTy >::SearchBin().

Referenced by MotifCluster::SpectralCut().

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

Here is the call graph for this function:

Here is the caller graph for this function:

int TCnCom::Len ( ) const
inline

Definition at line 101 of file cncom.h.

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

Referenced by GetRndNId(), and MotifCluster::SpectralCut().

101 { return NIdV.Len(); }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
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.

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 TVec< TVal, TSizeTy >::Save().

96 { NIdV.Save(SOut); }
TVec::Save
void Save(TSOut &SOut) const
Definition: ds.h:954
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.

13  {
14  FILE *F = fopen(FNm.CStr(), "wt");
15  if (! Desc.Empty()) { fprintf(F, "# %s\n", Desc.CStr()); }
16  fprintf(F, "# Connected Components:\t%d\n", CnComV.Len());
17  fprintf(F, "# Connected components (format: <Size>\\t<NodeId1>\\t<NodeId2>...)\n");
18  for (int cc = 0; cc < CnComV.Len(); cc++) {
19  const TIntV& NIdV = CnComV[cc].NIdV;
20  fprintf(F, "%d", NIdV.Len());
21  for (int i = 0; i < NIdV.Len(); i++) { fprintf(F, "\t%d", NIdV[i].Val); }
22  fprintf(F, "\n");
23  }
24  fclose(F);
25 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TCnCom::NIdV
TIntV NIdV
Definition: cncom.h:90
TStr::Empty
bool Empty() const
Definition: dt.h:491
TStr::CStr
char * CStr()
Definition: dt.h:479

Here is the call graph for this function:

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

Definition at line 109 of file cncom.h.

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

109 { NIdV.Sort(Asc); }
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TCnCom::NIdV
TIntV NIdV
Definition: cncom.h:90

Here is the call graph for this function:

Member Data Documentation

TIntV TCnCom::NIdV

Definition at line 90 of file cncom.h.

Referenced by Dump(), operator()(), operator<(), operator=(), operator==(), SaveTxt(), and MotifCluster::SpectralCut().

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