TCnCom Class Reference

#include <cncom.h>

List of all members.

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

---

Detailed Description

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

Definition at line 86 of file cncom.h.

---

Constructor & Destructor Documentation

TCnCom::TCnCom

(

)

[inline]

Definition at line 90 of file cncom.h.

: NIdV() { }

TCnCom::TCnCom

(

const TIntV &

NodeIdV

)

[inline]

Definition at line 91 of file cncom.h.

: NIdV(NodeIdV) { }

TCnCom::TCnCom

(

const TCnCom &

CC

)

[inline]

Definition at line 92 of file cncom.h.

: NIdV(CC.NIdV) { }

TCnCom::TCnCom

(

TSIn &

SIn

)

[inline]

Definition at line 93 of file cncom.h.

: NIdV(SIn) { }

---

Member Function Documentation

void TCnCom::Add

(

const int &

NodeId

)

[inline]

Definition at line 102 of file cncom.h.

{ NIdV.Add(NodeId); }

void TCnCom::Clr

(

)

[inline]

Definition at line 101 of file cncom.h.

{ NIdV.Clr(); }

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

Definition at line 3 of file cncom.cpp.

                                                         {
  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]

Definition at line 100 of file cncom.h.

{ return NIdV.Empty(); }

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 119 of file cncom.h.

                                                                 {
  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.

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

bool TCnCom::IsNIdIn

(

const int &

NId

)

const [inline]

Definition at line 107 of file cncom.h.

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

int TCnCom::Len

(

)

const [inline]

Definition at line 99 of file cncom.h.

{ return NIdV.Len(); }

const TIntV& TCnCom::operator()

(

)

const [inline]

Definition at line 104 of file cncom.h.

{ return NIdV; }

TIntV& TCnCom::operator()

(

)

[inline]

Definition at line 105 of file cncom.h.

{ return NIdV; }

bool TCnCom::operator<

(

const TCnCom &

CC

)

const [inline]

Definition at line 97 of file cncom.h.

{ return NIdV < CC.NIdV; }

TCnCom& TCnCom::operator=

(

const TCnCom &

CC

)

[inline]

Definition at line 95 of file cncom.h.

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

bool TCnCom::operator==

(

const TCnCom &

CC

)

const [inline]

Definition at line 96 of file cncom.h.

{ return NIdV == CC.NIdV; }

const TInt& TCnCom::operator[]

(

const int &

NIdN

)

const [inline]

Definition at line 103 of file cncom.h.

{ return NIdV[NIdN]; }

void TCnCom::Save

(

TSOut &

SOut

)

const [inline]

Definition at line 94 of file cncom.h.

{ NIdV.Save(SOut); }

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

Definition at line 13 of file cncom.cpp.

                                                                             {
  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 106 of file cncom.h.

{ NIdV.Sort(Asc); }

---

Member Data Documentation

TIntV TCnCom::NIdV

Definition at line 88 of file cncom.h.

---

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

• snap-core/cncom.h
• snap-core/cncom.cpp