SNAP Library 2.1, Developer Reference  2013-09-25 10:47:25
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
TKCore< PGraph > Class Template Reference

#include <kcore.h>

Collaboration diagram for TKCore< PGraph >:

List of all members.

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).
int GetCoreEdges () const
 Gets the number of edges in the K-core (for the current value of K).
const TIntVGetNIdV () const
 Returns the IDs of the nodes in the current K-core.
PGraph GetCoreG () const
 Returrns the graph of the current K-core.

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(), TKCore< PGraph >::Graph, and TKCore< PGraph >::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(), and TKCore< PGraph >::NIdV.

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.

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

template<class PGraph>
TIntV TKCore< PGraph >::NIdV [private]

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