TKCore< PGraph > Class Template Reference

#include <kcore.h>

Collaboration diagram for TKCore< PGraph >:

Public Member Functions
	TKCore (const PGraph &_Graph)
int	GetCurK () const
int	GetNextCore ()
int	GetCoreK (const int &K)
int	GetCoreNodes () const
	Gets the number of nodes in the K-core (for the current value of K). More...
int	GetCoreEdges () const
	Gets the number of edges in the K-core (for the current value of K). More...
const TIntV &	GetNIdV () const
	Returns the IDs of the nodes in the current K-core. More...
PGraph	GetCoreG () const
	Returrns the graph of the current K-core. More...

Private Member Functions
void	Init ()

Private Attributes
PGraph	Graph
TIntH	DegH
TInt	CurK
TIntV	NIdV

Detailed Description

template<class PGraph>
class TKCore< PGraph >

K-Core decomposition of a network. K-core is defined as a maximal subgraph of the original graph where every node points to at least K other nodes. K-core is obtained by repeatedly deleting nodes of degree < K from the graph until no nodes of degree < K exist. If the input graph is directed we treat it as undirected multigraph, i.e., we ignore the edge directions but there may be up to two edges between a pair of nodes. See the kcores example (examples/kcores/kcores.cpp) for how to use the code. For example: for (KCore(Graph); KCore.GetNextCore()!=0; ) { } will produce a sequence of K-cores for K=1...

Definition at line 11 of file kcore.h.

Constructor & Destructor Documentation

template<class PGraph>

TKCore< PGraph >::TKCore ( const PGraph &  _Graph )

inline

Definition at line 20 of file kcore.h.

References TKCore< PGraph >::Init().

: Graph(_Graph) { Init(); }

Here is the call graph for this function:

Member Function Documentation

template<class PGraph >

int TKCore< PGraph >::GetCoreEdges

(

)

const

Gets the number of edges in the K-core (for the current value of K).

Definition at line 53 of file kcore.h.

Referenced by TSnap::GetKCoreEdges().

                                       {
  int CoreEdges = 0;
  for (int k = DegH.FFirstKeyId(); DegH.FNextKeyId(k); ) {
    CoreEdges += DegH[k];
  }
  return CoreEdges/2;
}

Here is the caller graph for this function:

template<class PGraph>

PGraph TKCore< PGraph >::GetCoreG ( ) const

inline

Returrns the graph of the current K-core.

Definition at line 39 of file kcore.h.

References TSnap::GetSubGraph().

{ return TSnap::GetSubGraph(Graph, NIdV); }

Here is the call graph for this function:

template<class PGraph >

int TKCore< PGraph >::GetCoreK

(

const int &

K

)

Directly generates the core of order K. The function has the same effect as calling GetNextCore() K times.

Definition at line 94 of file kcore.h.

Referenced by TSnap::GetKCore().

                                         {
  Init();
  CurK = K-1;
  return GetNextCore();
}

Here is the caller graph for this function:

template<class PGraph>

int TKCore< PGraph >::GetCoreNodes ( ) const

inline

Gets the number of nodes in the K-core (for the current value of K).

Definition at line 33 of file kcore.h.

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

Referenced by TSnap::GetKCoreNodes().

{ return NIdV.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph>

int TKCore< PGraph >::GetCurK ( ) const

inline

Gets the currrent value of K. For every call of GetNextCore() the value of K increases by 1.

Definition at line 23 of file kcore.h.

References TKCore< PGraph >::CurK.

Referenced by TSnap::GetKCoreEdges(), and TSnap::GetKCoreNodes().

{ return CurK; } 

Here is the caller graph for this function:

template<class PGraph >

int TKCore< PGraph >::GetNextCore

(

)

Returns the number of nodes in the next (K=K+1) core. The function starts with K=1-core and every time we call it it increases the value of K by 1 and generates the core. The function proceeds until GetCoreNodes() returns 0. Return value of the function is the size (the number of nodes) in the K-core (for the current value of K).

Definition at line 62 of file kcore.h.

Referenced by TSnap::GetKCoreEdges(), and TSnap::GetKCoreNodes().

                                {
  TIntV DelV;
  int NDel=-1, AllDeg=0; //Pass=1;
  TExeTm ExeTm;
  CurK++;
  //printf("Get K-core: %d\n", CurK());
  while (NDel != 0) {
    NDel = 0;
    for (int k = DegH.FFirstKeyId(); DegH.FNextKeyId(k); ) {
      const int NId = DegH.GetKey(k);
      const int Deg = DegH[k];
      if (Deg < CurK) {
        const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
        for (int e = 0; e < NI.GetDeg(); e++) {
          const int n = NI.GetNbrNId(e);
          const int nk = DegH.GetKeyId(n);
          if (nk != -1) { DegH[nk] -= 1; } // mark node deleted
        }
        DegH.DelKeyId(k);
        NDel++;  AllDeg++;
      }
    }
    //printf("\r  pass %d]  %d deleted,  %d all deleted  [%s]", Pass++, NDel, AllDeg, ExeTm.GetStr());
  }
  //printf("\n");
  DegH.Defrag();
  DegH.GetKeyV(NIdV);
  NIdV.Sort();
  return NIdV.Len(); // all nodes in the current core
}

Here is the caller graph for this function:

template<class PGraph>

const TIntV& TKCore< PGraph >::GetNIdV ( ) const

inline

Returns the IDs of the nodes in the current K-core.

Definition at line 37 of file kcore.h.

References TKCore< PGraph >::NIdV.

Referenced by TSnap::GetKCore().

{ return NIdV; }

Here is the caller graph for this function:

template<class PGraph >

void TKCore< PGraph >::Init ( )

private

Definition at line 43 of file kcore.h.

Referenced by TKCore< PGraph >::TKCore().

                          {
  DegH.Gen(Graph->GetNodes());
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    //DegH.AddDat(NI.GetId(), NI.GetOutDeg());
    DegH.AddDat(NI.GetId(), NI.GetDeg());
  }
  CurK = 0;
}

Here is the caller graph for this function:

Member Data Documentation

template<class PGraph>

TInt TKCore< PGraph >::CurK

private

Definition at line 15 of file kcore.h.

Referenced by TKCore< PGraph >::GetCurK().

template<class PGraph>

TIntH TKCore< PGraph >::DegH

private

Definition at line 14 of file kcore.h.

template<class PGraph>

PGraph TKCore< PGraph >::Graph

private

Definition at line 13 of file kcore.h.

template<class PGraph>

TIntV TKCore< PGraph >::NIdV

private

Definition at line 16 of file kcore.h.

Referenced by TKCore< PGraph >::GetNIdV().

---

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

• snap-core/kcore.h