SNAP Library 2.3, User Reference  2014-06-16 11:58:46
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
kcore.h
Go to the documentation of this file.
1 // TODO ROK, Jure included basic documentation, finalize reference doc
2 
3 //#//////////////////////////////////////////////
10 template<class PGraph>
11 class TKCore {
12 private:
13  PGraph Graph;
17 private:
18  void Init();
19 public:
20  TKCore(const PGraph& _Graph) : Graph(_Graph) { Init(); }
23  int GetCurK() const { return CurK; }
28  int GetNextCore();
31  int GetCoreK(const int& K);
33  int GetCoreNodes() const { return NIdV.Len(); }
35  int GetCoreEdges() const;
37  const TIntV& GetNIdV() const { return NIdV; }
39  PGraph GetCoreG() const { return TSnap::GetSubGraph(Graph, NIdV); }
40 };
41 
42 template<class PGraph>
44  DegH.Gen(Graph->GetNodes());
45  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
46  //DegH.AddDat(NI.GetId(), NI.GetOutDeg());
47  DegH.AddDat(NI.GetId(), NI.GetDeg());
48  }
49  CurK = 0;
50 }
51 
52 template<class PGraph>
54  int CoreEdges = 0;
55  for (int k = DegH.FFirstKeyId(); DegH.FNextKeyId(k); ) {
56  CoreEdges += DegH[k];
57  }
58  return CoreEdges/2;
59 }
60 
61 template<class PGraph>
63  TIntV DelV;
64  int NDel=-1, AllDeg=0; //Pass=1;
65  TExeTm ExeTm;
66  CurK++;
67  //printf("Get K-core: %d\n", CurK());
68  while (NDel != 0) {
69  NDel = 0;
70  for (int k = DegH.FFirstKeyId(); DegH.FNextKeyId(k); ) {
71  const int NId = DegH.GetKey(k);
72  const int Deg = DegH[k];
73  if (Deg < CurK) {
74  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
75  for (int e = 0; e < NI.GetDeg(); e++) {
76  const int n = NI.GetNbrNId(e);
77  const int nk = DegH.GetKeyId(n);
78  if (nk != -1) { DegH[nk] -= 1; } // mark node deleted
79  }
80  DegH.DelKeyId(k);
81  NDel++; AllDeg++;
82  }
83  }
84  //printf("\r pass %d] %d deleted, %d all deleted [%s]", Pass++, NDel, AllDeg, ExeTm.GetStr());
85  }
86  //printf("\n");
87  DegH.Defrag();
88  DegH.GetKeyV(NIdV);
89  NIdV.Sort();
90  return NIdV.Len(); // all nodes in the current core
91 }
92 
93 template<class PGraph>
94 int TKCore<PGraph>::GetCoreK(const int& K) {
95  Init();
96  CurK = K-1;
97  return GetNextCore();
98 }
99 
101 // Snap
102 namespace TSnap {
105 template<class PGraph>
106 PGraph GetKCore(const PGraph& Graph, const int& K) {
107  TKCore<PGraph> KCore(Graph);
108  KCore.GetCoreK(K);
109  return TSnap::GetSubGraph(Graph, KCore.GetNIdV());
110 }
111 
113 template<class PGraph>
114 int GetKCoreNodes(const PGraph& Graph, TIntPrV& CoreIdSzV) {
115  TKCore<PGraph> KCore(Graph);
116  CoreIdSzV.Clr();
117  CoreIdSzV.Add(TIntPr(0, Graph->GetNodes()));
118  for (int i = 1; KCore.GetNextCore() > 0; i++) {
119  CoreIdSzV.Add(TIntPr(i, KCore.GetCoreNodes()));
120  }
121  return KCore.GetCurK();
122 }
123 
125 template<class PGraph>
126 int GetKCoreEdges(const PGraph& Graph, TIntPrV& CoreIdSzV) {
127  TKCore<PGraph> KCore(Graph);
128  CoreIdSzV.Clr();
129  CoreIdSzV.Add(TIntPr(0, Graph->GetEdges()));
130  for (int i = 1; KCore.GetNextCore() > 0; i++) {
131  CoreIdSzV.Add(TIntPr(i, KCore.GetCoreEdges()));
132  }
133  return KCore.GetCurK();
134 }
135 
136 } // namespace TSnap
const TIntV & GetNIdV() const
Returns the IDs of the nodes in the current K-core.
Definition: kcore.h:37
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TInt CurK
Definition: kcore.h:15
int GetKCoreNodes(const PGraph &Graph, TIntPrV &CoreIdSzV)
Returns the number of nodes in each core of order K (where K=0, 1, ...)
Definition: kcore.h:114
Definition: tm.h:354
int GetNextCore()
Definition: kcore.h:62
int GetCoreK(const int &K)
Definition: kcore.h:94
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
PGraph Graph
Definition: kcore.h:13
int GetCoreNodes() const
Gets the number of nodes in the K-core (for the current value of K).
Definition: kcore.h:33
int GetCurK() const
Definition: kcore.h:23
PGraph GetCoreG() const
Returrns the graph of the current K-core.
Definition: kcore.h:39
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
TIntV NIdV
Definition: kcore.h:16
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
int GetKCoreEdges(const PGraph &Graph, TIntPrV &CoreIdSzV)
Returns the number of edges in each core of order K (where K=0, 1, ...)
Definition: kcore.h:126
int GetCoreEdges() const
Gets the number of edges in the K-core (for the current value of K).
Definition: kcore.h:53
Definition: dt.h:1041
void Init()
Definition: kcore.h:43
PGraph GetKCore(const PGraph &Graph, const int &K)
Definition: kcore.h:106
TKCore(const PGraph &_Graph)
Definition: kcore.h:20
Definition: kcore.h:11
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
TIntH DegH
Definition: kcore.h:14