SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
TCnCom Class Reference

#include <cncom.h>

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() ()
 
const TIntGetVal (const int &NIdN) const
 
void Sort (const bool &Asc=true)
 
bool IsNIdIn (const int &NId) const
 
const TIntGetRndNId () 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() { }
TIntV NIdV
Definition: cncom.h:90
TCnCom::TCnCom ( const TIntV NodeIdV)
inline

Definition at line 93 of file cncom.h.

93 : NIdV(NodeIdV) { }
TIntV NIdV
Definition: cncom.h:90
TCnCom::TCnCom ( const TCnCom CC)
inline

Definition at line 94 of file cncom.h.

94 : NIdV(CC.NIdV) { }
TIntV NIdV
Definition: cncom.h:90
TCnCom::TCnCom ( TSIn SIn)
inline

Definition at line 95 of file cncom.h.

95 : NIdV(SIn) { }
TIntV NIdV
Definition: cncom.h:90

Member Function Documentation

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

Definition at line 104 of file cncom.h.

104 { NIdV.Add(NodeId); }
TIntV NIdV
Definition: cncom.h:90
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void TCnCom::Clr ( )
inline

Definition at line 103 of file cncom.h.

103 { NIdV.Clr(); }
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TIntV NIdV
Definition: cncom.h:90
void TCnCom::Dump ( const TCnComV CnComV,
const TStr Desc = TStr() 
)
static

Definition at line 3 of file cncom.cpp.

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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV NIdV
Definition: cncom.h:90
bool Empty() const
Definition: dt.h:488
char * CStr()
Definition: dt.h:476
bool TCnCom::Empty ( ) const
inline

Definition at line 102 of file cncom.h.

102 { return NIdV.Empty(); }
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TIntV NIdV
Definition: cncom.h:90
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.

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 }
Definition: ds.h:129
TVal1 Val1
Definition: ds.h:131
TVal2 Val2
Definition: ds.h:132
Definition: ds.h:2509
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:170
TVal3 Val3
Definition: ds.h:133
int TCnCom::GetPrimHashCd ( ) const
inline

Definition at line 119 of file cncom.h.

119 { return NIdV.GetPrimHashCd(); }
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:948
TIntV NIdV
Definition: cncom.h:90
const TInt& TCnCom::GetRndNId ( ) const
inline

Definition at line 111 of file cncom.h.

111 { return NIdV[TInt::Rnd.GetUniDevInt(Len())]; }
static TRnd Rnd
Definition: dt.h:1053
TIntV NIdV
Definition: cncom.h:90
int Len() const
Definition: cncom.h:101
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
int TCnCom::GetSecHashCd ( ) const
inline

Definition at line 120 of file cncom.h.

120 { return NIdV.GetSecHashCd(); }
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:960
TIntV NIdV
Definition: cncom.h:90
const TInt& TCnCom::GetVal ( const int &  NIdN) const
inline

Definition at line 108 of file cncom.h.

108 { return operator[](NIdN); }
const TInt & operator[](const int &NIdN) const
Definition: cncom.h:105
bool TCnCom::IsNIdIn ( const int &  NId) const
inline

Definition at line 110 of file cncom.h.

110 { return NIdV.SearchBin(NId) != -1; }
TIntV NIdV
Definition: cncom.h:90
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1454
int TCnCom::Len ( ) const
inline

Definition at line 101 of file cncom.h.

101 { return NIdV.Len(); }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV NIdV
Definition: cncom.h:90
const TIntV& TCnCom::operator() ( ) const
inline

Definition at line 106 of file cncom.h.

106 { return NIdV; }
TIntV NIdV
Definition: cncom.h:90
TIntV& TCnCom::operator() ( )
inline

Definition at line 107 of file cncom.h.

107 { return NIdV; }
TIntV NIdV
Definition: cncom.h:90
bool TCnCom::operator< ( const TCnCom CC) const
inline

Definition at line 99 of file cncom.h.

99 { return NIdV < CC.NIdV; }
TIntV NIdV
Definition: cncom.h:90
TCnCom& TCnCom::operator= ( const TCnCom CC)
inline

Definition at line 97 of file cncom.h.

97 { if (this != &CC) NIdV = CC.NIdV; return *this; }
TIntV NIdV
Definition: cncom.h:90
bool TCnCom::operator== ( const TCnCom CC) const
inline

Definition at line 98 of file cncom.h.

98 { return NIdV == CC.NIdV; }
TIntV NIdV
Definition: cncom.h:90
const TInt& TCnCom::operator[] ( const int &  NIdN) const
inline

Definition at line 105 of file cncom.h.

105 { return NIdV[NIdN]; }
TIntV NIdV
Definition: cncom.h:90
void TCnCom::Save ( TSOut SOut) const
inline

Definition at line 96 of file cncom.h.

96 { NIdV.Save(SOut); }
void Save(TSOut &SOut) const
Definition: ds.h:903
TIntV NIdV
Definition: cncom.h:90
void TCnCom::SaveTxt ( const TCnComV CnComV,
const TStr FNm,
const TStr Desc = TStr() 
)
static

Definition at line 13 of file cncom.cpp.

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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV NIdV
Definition: cncom.h:90
bool Empty() const
Definition: dt.h:488
char * CStr()
Definition: dt.h:476
void TCnCom::Sort ( const bool &  Asc = true)
inline

Definition at line 109 of file cncom.h.

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

Member Data Documentation

TIntV TCnCom::NIdV

Definition at line 90 of file cncom.h.


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