SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
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
kcore.h
Go to the documentation of this file.
00001 // TODO ROK, Jure included basic documentation, finalize reference doc
00002 
00003 //#//////////////////////////////////////////////
00010 template<class PGraph>
00011 class TKCore {
00012 private:
00013   PGraph Graph;
00014   TIntH DegH;
00015   TInt CurK;
00016   TIntV NIdV;
00017 private:
00018   void Init();
00019 public:
00020   TKCore(const PGraph& _Graph) : Graph(_Graph) { Init(); }
00023   int GetCurK() const { return CurK; } 
00028   int GetNextCore();                   
00031   int GetCoreK(const int& K);
00033   int GetCoreNodes() const { return NIdV.Len(); }
00035   int GetCoreEdges() const;
00037   const TIntV& GetNIdV() const { return NIdV; }
00039   PGraph GetCoreG() const { return TSnap::GetSubGraph(Graph, NIdV); }
00040 };
00041 
00042 template<class PGraph>
00043 void TKCore<PGraph>::Init() {
00044   DegH.Gen(Graph->GetNodes());
00045   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00046     //DegH.AddDat(NI.GetId(), NI.GetOutDeg());
00047     DegH.AddDat(NI.GetId(), NI.GetDeg());
00048   }
00049   CurK = 0;
00050 }
00051 
00052 template<class PGraph>
00053 int TKCore<PGraph>::GetCoreEdges() const {
00054   int CoreEdges = 0;
00055   for (int k = DegH.FFirstKeyId(); DegH.FNextKeyId(k); ) {
00056     CoreEdges += DegH[k];
00057   }
00058   return CoreEdges/2;
00059 }
00060 
00061 template<class PGraph>
00062 int TKCore<PGraph>::GetNextCore() {
00063   TIntV DelV;
00064   int NDel=-1, Pass=1, AllDeg=0;
00065   TExeTm ExeTm;
00066   CurK++;
00067   printf("Get K-core: %d\n", CurK());
00068   while (NDel != 0) {
00069     NDel = 0;
00070     for (int k = DegH.FFirstKeyId(); DegH.FNextKeyId(k); ) {
00071       const int NId = DegH.GetKey(k);
00072       const int Deg = DegH[k];
00073       if (Deg < CurK) {
00074         const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
00075         for (int e = 0; e < NI.GetDeg(); e++) {
00076           const int n = NI.GetNbrNId(e);
00077           const int nk = DegH.GetKeyId(n);
00078           if (nk != -1) { DegH[nk] -= 1; } // mark node deleted
00079         }
00080         DegH.DelKeyId(k);
00081         NDel++;  AllDeg++;
00082       }
00083     }
00084     printf("\r  pass %d]  %d deleted,  %d all deleted  [%s]", Pass++, NDel, AllDeg, ExeTm.GetStr());
00085   }
00086   printf("\n");
00087   DegH.Defrag();
00088   DegH.GetKeyV(NIdV);
00089   NIdV.Sort();
00090   return NIdV.Len(); // all nodes in the current core
00091 }
00092 
00093 template<class PGraph>
00094 int TKCore<PGraph>::GetCoreK(const int& K) {
00095   Init();
00096   CurK = K-1;
00097   return GetNextCore();
00098 }
00099 
00101 // Snap
00102 namespace TSnap {
00105 template<class PGraph>
00106 PGraph GetKCore(const PGraph& Graph, const int& K) {
00107   TKCore<PGraph> KCore(Graph);
00108   KCore.GetCoreK(K);
00109   return TSnap::GetSubGraph(Graph, KCore.GetNIdV());
00110 }
00111 
00112 } // namespace TSnap