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

: NIdV() { }

TCnCom::TCnCom ( const TIntV &  NodeIdV )

inline

Definition at line 93 of file cncom.h.

: NIdV(NodeIdV) { }

TCnCom::TCnCom ( const TCnCom &  CC )

inline

Definition at line 94 of file cncom.h.

: NIdV(CC.NIdV) { }

TCnCom::TCnCom ( TSIn &  SIn )

inline

Definition at line 95 of file cncom.h.

: NIdV(SIn) { }

Member Function Documentation

void TCnCom::Add ( const int &  NodeId )

inline

Definition at line 104 of file cncom.h.

{ NIdV.Add(NodeId); }

void TCnCom::Clr ( )

inline

Definition at line 103 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 102 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 124 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
      }
    }
  }
}

int TCnCom::GetPrimHashCd ( ) const

inline

Definition at line 119 of file cncom.h.

{ return NIdV.GetPrimHashCd(); }

const TInt& TCnCom::GetRndNId ( ) const

inline

Definition at line 111 of file cncom.h.

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

int TCnCom::GetSecHashCd ( ) const

inline

Definition at line 120 of file cncom.h.

{ return NIdV.GetSecHashCd(); }

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

inline

Definition at line 108 of file cncom.h.

{ return operator[](NIdN); }

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

inline

Definition at line 110 of file cncom.h.

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

int TCnCom::Len ( ) const

inline

Definition at line 101 of file cncom.h.

{ return NIdV.Len(); }

const TIntV& TCnCom::operator() ( ) const

inline

Definition at line 106 of file cncom.h.

{ return NIdV; }

TIntV& TCnCom::operator() ( )

inline

Definition at line 107 of file cncom.h.

{ return NIdV; }

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

inline

Definition at line 99 of file cncom.h.

{ return NIdV < CC.NIdV; }

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

inline

Definition at line 97 of file cncom.h.

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

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

inline

Definition at line 98 of file cncom.h.

{ return NIdV == CC.NIdV; }

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

inline

Definition at line 105 of file cncom.h.

{ return NIdV[NIdN]; }

void TCnCom::Save ( TSOut &  SOut ) const

inline

Definition at line 96 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 109 of file cncom.h.

{ NIdV.Sort(Asc); }

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:

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