|
SNAP Library 2.0, Developer Reference
2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
|
SNAP Library 2.0, Developer Reference
2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
#include <cncom.h>
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() () |
| void | Sort (const bool &Asc=true) |
| bool | IsNIdIn (const int &NId) const |
| const TInt & | GetRndNId () 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 |
Connected Component. Connected component is defined by a vector of its node IDs.
| TCnCom::TCnCom | ( | ) | [inline] |
| TCnCom::TCnCom | ( | const TIntV & | NodeIdV | ) | [inline] |
| TCnCom::TCnCom | ( | const TCnCom & | CC | ) | [inline] |
| TCnCom::TCnCom | ( | TSIn & | SIn | ) | [inline] |
| void TCnCom::Add | ( | const int & | NodeId | ) | [inline] |
Definition at line 102 of file cncom.h.
References TVec< TVal, TSizeTy >::Add(), and NIdV.
Referenced by TSccVisitor< PGraph, OnlyCount >::FinishNode().
| void TCnCom::Clr | ( | ) | [inline] |
| 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");
}
}
| bool TCnCom::Empty | ( | ) | const [inline] |
| 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 119 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
}
}
}
}
| const TInt& TCnCom::GetRndNId | ( | ) | const [inline] |
Definition at line 108 of file cncom.h.
References TRnd::GetUniDevInt(), Len(), NIdV, and TInt::Rnd.
{ return NIdV[TInt::Rnd.GetUniDevInt(Len())]; }
| bool TCnCom::IsNIdIn | ( | const int & | NId | ) | const [inline] |
| int TCnCom::Len | ( | ) | const [inline] |
Definition at line 99 of file cncom.h.
References TVec< TVal, TSizeTy >::Len(), and NIdV.
Referenced by GetRndNId().
| const TIntV& TCnCom::operator() | ( | ) | const [inline] |
| TIntV& TCnCom::operator() | ( | ) | [inline] |
| bool TCnCom::operator< | ( | const TCnCom & | CC | ) | const [inline] |
| bool TCnCom::operator== | ( | const TCnCom & | CC | ) | const [inline] |
| const TInt& TCnCom::operator[] | ( | const int & | NIdN | ) | const [inline] |
| void TCnCom::Save | ( | TSOut & | SOut | ) | const [inline] |
| 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);
}
| void TCnCom::Sort | ( | const bool & | Asc = true | ) | [inline] |
Definition at line 88 of file cncom.h.
Referenced by Add(), Clr(), Dump(), Empty(), GetRndNId(), IsNIdIn(), Len(), operator()(), operator<(), operator=(), operator==(), operator[](), Save(), SaveTxt(), and Sort().
1.8.0 