SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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
Main namespace for all the Snap global entities.
Definition: alg.h:1
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:355
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:575
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:1022
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:1137
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:602
TIntH DegH
Definition: kcore.h:14