gbase.h

Go to the documentation of this file.

// Defines
#define Kilo(n) (1000*(n))
#define Mega(n) (1000*1000*(n))
#define Giga(n) (1000*1000*1000*(n))

//#//////////////////////////////////////////////

typedef enum TGraphFlag_ {
  gfUndef=0,    
  gfDirected,   
  gfMultiGraph, 
  gfNodeDat,    
  gfEdgeDat,    
  gfSources,    
  gfBipart,     
  gfMx          
} TGraphFlag;

namespace TSnap {

template <class TGraph> struct IsDirected   { enum { Val = 0 }; };
template <class TGraph> struct IsMultiGraph { enum { Val = 0 }; };
template <class TGraph> struct IsNodeDat    { enum { Val = 0 }; };
template <class TGraph> struct IsEdgeDat    { enum { Val = 0 }; };
template <class TGraph> struct IsSources    { enum { Val = 0 }; };
template <class TGraph> struct IsBipart     { enum { Val = 0 }; };

#define HasGraphFlag(TGraph, Flag) \
  ((Flag)==gfDirected ? TSnap::IsDirected<TGraph::TNet>::Val : \
  (Flag)==gfMultiGraph ? TSnap::IsMultiGraph<TGraph::TNet>::Val : \
  (Flag)==gfNodeDat ? TSnap::IsNodeDat<TGraph::TNet>::Val : \
  (Flag)==gfEdgeDat ? TSnap::IsEdgeDat<TGraph::TNet>::Val : \
  (Flag)==gfSources ? TSnap::IsSources<TGraph::TNet>::Val : \
  (Flag)==gfBipart ? TSnap::IsBipart<TGraph::TNet>::Val : 0)

#if 0
// RS 2013/08/19, commented out IsDerivedFrom, it is not called anywhere
//  swig throws an error
template<class TDerivClass, class TBaseClass>
class IsDerivedFrom {
private:
  struct Yes { char a[1]; };
  struct No { char a[10]; };
  static Yes Test(TBaseClass*);
  static No Test(...);         // undefined
public:
  enum { Val = sizeof(Test(static_cast<TDerivClass*>(0))) == sizeof(Yes) ? 1 : 0 };
};
#endif

// Graph Base

TStr GetFlagStr(const TGraphFlag& GraphFlag);

template <class PGraph> void PrintInfo(const PGraph& Graph, const TStr& Desc="", const TStr& OutFNm="", const bool& Fast=true);

// Implementation

// Forward declaration, definition in triad.h
template <class PGraph> int64 GetTriads(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes=-1);
template <class PGraph> double GetBfsEffDiam(const PGraph& Graph, const int& NTestNodes, const bool& IsDir, double& EffDiam, int& FullDiam);
template <class PGraph> double GetMxWccSz(const PGraph& Graph);
template <class PGraph> double GetMxSccSz(const PGraph& Graph);
template<class PGraph> int GetKCoreNodes(const PGraph& Graph, TIntPrV& CoreIdSzV);
template<class PGraph> int GetKCoreEdges(const PGraph& Graph, TIntPrV& CoreIdSzV);

template <class PGraph>
void PrintInfo(const PGraph& Graph, const TStr& Desc, const TStr& OutFNm, const bool& Fast) {
  int BiDirEdges=0, ZeroNodes=0, ZeroInNodes=0, ZeroOutNodes=0, SelfEdges=0, NonZIODegNodes=0;
  THash<TIntPr, TInt> UniqDirE, UniqUnDirE;
  FILE *F = stdout;
  if (! OutFNm.Empty()) F = fopen(OutFNm.CStr(), "wt");
  if (! Desc.Empty()) { fprintf(F, "%s:", Desc.CStr()); }
  else { fprintf(F, "Graph:"); }
  for (int f = gfUndef; f < gfMx; f++) {
    if (HasGraphFlag(typename PGraph::TObj, TGraphFlag(f))) {
      fprintf(F, " %s", TSnap::GetFlagStr(TGraphFlag(f)).CStr()); }
  }
  // calc stat
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetDeg()==0) ZeroNodes++;
    if (NI.GetInDeg()==0) ZeroInNodes++;
    if (NI.GetOutDeg()==0) ZeroOutNodes++;
    if (NI.GetInDeg()!=0 && NI.GetOutDeg()!=0) NonZIODegNodes++;
    if (! Fast || Graph->GetNodes() < 1000) {
      const int NId = NI.GetId();
      for (int edge = 0; edge < NI.GetOutDeg(); edge++) {
        const int DstNId = NI.GetOutNId(edge);
        if (Graph->IsEdge(DstNId, NId)) BiDirEdges++;
        if (NId == DstNId) SelfEdges++;
        UniqDirE.AddKey(TIntPr(NId, DstNId));
        UniqUnDirE.AddKey(TIntPr(TInt::GetMn(NId, DstNId), TInt::GetMx(NId, DstNId)));
      }
    }
  }
  int64 Closed=0, Open=0;
  double WccSz=0, SccSz=0;
  double EffDiam=0;
  int FullDiam=0;
  if (! Fast) {
    TSnap::GetTriads(Graph, Closed, Open);
    WccSz = TSnap::GetMxWccSz(Graph);
    SccSz = TSnap::GetMxSccSz(Graph);
    TSnap::GetBfsEffDiam(Graph, 100, false, EffDiam, FullDiam);
  }
  // print info
  fprintf(F, "\n");
  fprintf(F, "  Nodes:                    %d\n", Graph->GetNodes());
  fprintf(F, "  Edges:                    %d\n", Graph->GetEdges());
  fprintf(F, "  Zero Deg Nodes:           %d\n", ZeroNodes);
  fprintf(F, "  Zero InDeg Nodes:         %d\n", ZeroInNodes);
  fprintf(F, "  Zero OutDeg Nodes:        %d\n", ZeroOutNodes);
  fprintf(F, "  NonZero In-Out Deg Nodes: %d\n", NonZIODegNodes);
  if (! Fast) {
    fprintf(F, "  Unique directed edges:    %d\n", UniqDirE.Len());
    fprintf(F, "  Unique undirected edges:  %d\n", UniqUnDirE.Len());
    fprintf(F, "  Self Edges:               %d\n", SelfEdges);
    fprintf(F, "  BiDir Edges:              %d\n", BiDirEdges);
    fprintf(F, "  Closed triangles:         %s\n", TUInt64::GetStr(Closed).CStr());
    fprintf(F, "  Open triangles:           %s\n", TUInt64::GetStr(Open).CStr());
    fprintf(F, "  Frac. of closed triads:   %f\n", Closed/double(Closed+Open));
    fprintf(F, "  Connected component size: %f\n", WccSz);
    fprintf(F, "  Strong conn. comp. size:  %f\n", SccSz);
    fprintf(F, "  Approx. full diameter:    %d\n", FullDiam);
    fprintf(F, "  90%% effective diameter:  %f\n", EffDiam);
    //fprintf(F, "  Core\tNodes\tEdges\n");
    //for (int i  = 0; i < CNodesV.Len(); i++) {
    //  printf("  %d\t%d\t%d\n", CNodesV[i].Val1(), CNodesV[i].Val2(), CEdgesV[i].Val2());
    //}
  }
  if (! OutFNm.Empty()) { fclose(F); }
}

}  // namespace TSnap

//#//////////////////////////////////////////////
template <class TVal>
class TSnapQueue {
private:
  TInt MxFirst; // how often we move the queue to the start of the array
  TInt First, Last;
  TVec<TVal> ValV;
public:
  TSnapQueue() : MxFirst(1024), First(0), Last(0), ValV(MxFirst, 0) { }
  TSnapQueue(const int& MxVals) : MxFirst(1024+MxVals/10), First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
  TSnapQueue(const int& MxVals, const int& MaxFirst) : MxFirst(MaxFirst),
    First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
  TSnapQueue(const TSnapQueue& Queue) : MxFirst(Queue.MxFirst), First(Queue.First), Last(Queue.Last), ValV(Queue.ValV) { }
  explicit TSnapQueue(TSIn& SIn): MxFirst(SIn), First(SIn), Last(SIn), ValV(SIn) { }
  void Save(TSOut& SOut) const { MxFirst.Save(SOut); First.Save(SOut); Last.Save(SOut); ValV.Save(SOut); }

  TSnapQueue& operator=(const TSnapQueue& Queue) { if (this != &Queue) { MxFirst=Queue.MxFirst;
    First=Queue.First; Last=Queue.Last; ValV=Queue.ValV; } return *this; }
  const TVal& operator[](const int& ValN) const { return ValV[First+ValN]; }

  void Clr(const bool& DoDel=true) { ValV.Clr(DoDel);  First=Last=0; }
  void Gen(const int& MxVals, const int& MaxFirst=1024) {
    MxFirst=MaxFirst; First=Last=0; ValV.Gen(MxVals, 0); }

  bool Empty() const {return First==Last;}
  int Len() const {return Last-First;}
  int GetFirst() const { return First; }
  int GetLast() const { return Last; }
  int Reserved() const { return ValV.Reserved(); }

  const TVal& Top() const { return ValV[First]; }
  void Pop() { First++;
    if (First==Last) { ValV.Clr(false); First=Last=0; } }
  void Push(const TVal& Val) {
    if (First>0 && (First > MxFirst || ValV.Len() == ValV.Reserved()) && ! ValV.Empty()) {
      //printf("[move cc queue.Len:%d-->%d]", ValV.Len(),Len()); TExeTm Tm;
      memmove(ValV.BegI(), ValV.GetI(First), sizeof(TVal)*Len());
      ValV.Del(Len(), ValV.Len()-1);  Last-=First;  First=0;
      //printf("[%s]\n", Tm.GetStr()); fflush(stdout);
    }
    //if (ValV.Len() == ValV.Reserved()){ printf("[resizeCCQ]"); fflush(stdout); }
    Last++;  ValV.Add(Val);
  }
};

//#//////////////////////////////////////////////

class TUnionFind {
private:
  THash<TInt, TIntPr> KIdSetH; // key id to (parent, rank)
public:
  TInt& Parent(const int& Key) { return KIdSetH.GetDat(Key).Val1; }
  TInt& Rank(const int& Key) { return KIdSetH.GetDat(Key).Val2; }
public:
  TUnionFind() : KIdSetH() { }
  TUnionFind(const int& ExpectKeys) : KIdSetH(ExpectKeys, true) { }
  TUnionFind(const TUnionFind& UnionFind) : KIdSetH(UnionFind.KIdSetH) { }
  TUnionFind& operator = (const TUnionFind& UF) { KIdSetH=UF.KIdSetH; return *this; }

  int Len() const { return KIdSetH.Len(); }
  bool IsKey(const int& Key) const { return KIdSetH.IsKey(Key); }
  int GetKeyI(const int& KeyN) const { return KIdSetH.GetKey(KeyN); }
  int Find(const int& Key);
  int Add(const int& Key) { KIdSetH.AddDat(Key, TIntPr(-1, 0));  return Key; }
  void Union(const int& Key1, const int& Key2);
  bool IsSameSet(const int& Key1, const int& Key2) {
    return Find(Key1) == Find(Key2); }
  void Dump();
};

//#//////////////////////////////////////////////

template <class TVal, class TCmp = TLss<TVal> >
class THeap {
private:
  TCmp Cmp;
  TVec<TVal> HeapV;
private:
  void PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val);
  void AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val);
  void MakeHeap(const int& First, const int& Len);
public:
  THeap() : HeapV() { }
  THeap(const int& MxVals) : Cmp(), HeapV(MxVals, 0) { }
  THeap(const TCmp& _Cmp) : Cmp(_Cmp), HeapV() { }
  THeap(const TVec<TVal>& Vec) : Cmp(), HeapV(Vec) { MakeHeap(); }
  THeap(const TVec<TVal>& Vec, const TCmp& _Cmp) : Cmp(_Cmp), HeapV(Vec) { MakeHeap(); }
  THeap(const THeap& Heap) : Cmp(Heap.Cmp), HeapV(Heap.HeapV) { }
  THeap& operator = (const THeap& H) { Cmp=H.Cmp; HeapV=H.HeapV; return *this; }

  const TVal& TopHeap() const { return HeapV[0]; }
  void PushHeap(const TVal& Val);
  TVal PopHeap();
  int Len() const { return HeapV.Len(); }
  bool Empty() const { return HeapV.Empty(); }
  const TVec<TVal>& operator()() const { return HeapV; }
  TVec<TVal>& operator()() { return HeapV; }
  void Add(const TVal& Val) { HeapV.Add(Val); }
  void MakeHeap() { MakeHeap(0, Len()); }
};

template <class TVal, class TCmp>
void THeap<TVal, TCmp>::PushHeap(const TVal& Val) {
  HeapV.Add(Val);
  PushHeap(0, HeapV.Len()-1, 0, Val);
}

template <class TVal, class TCmp>
TVal THeap<TVal, TCmp>::PopHeap() {
  IAssert(! HeapV.Empty());
  const TVal Top = HeapV[0];
  HeapV[0] = HeapV.Last();
  HeapV.DelLast();
  if (! HeapV.Empty()) {
    AdjustHeap(0, 0, HeapV.Len(), HeapV[0]);
  }
  return Top;
}

template <class TVal, class TCmp>
void THeap<TVal, TCmp>::PushHeap(const int& First, int HoleIdx, const int& Top, TVal Val) {
  int Parent = (HoleIdx-1)/2;
  while (HoleIdx > Top && Cmp(HeapV[First+Parent], Val)) {
    HeapV[First+HoleIdx] = HeapV[First+Parent];
    HoleIdx = Parent;  Parent = (HoleIdx-1)/2;
  }
  HeapV[First+HoleIdx] = Val;
}

template <class TVal, class TCmp>
void THeap<TVal, TCmp>::AdjustHeap(const int& First, int HoleIdx, const int& Len, TVal Val) {
  const int Top = HoleIdx;
  int Right = 2*HoleIdx+2;
  while (Right < Len) {
    if (Cmp(HeapV[First+Right], HeapV[First+Right-1])) { Right--; }
    HeapV[First+HoleIdx] = HeapV[First+Right];
    HoleIdx = Right;  Right = 2*(Right+1); }
  if (Right == Len) {
    HeapV[First+HoleIdx] = HeapV[First+Right-1];
    HoleIdx = Right-1; }
  PushHeap(First, HoleIdx, Top, Val);
}

template <class TVal, class TCmp>
void THeap<TVal, TCmp>::MakeHeap(const int& First, const int& Len) {
  if (Len < 2) { return; }
  int Parent = (Len-2)/2;
  while (true) {
    AdjustHeap(First, Parent, Len, HeapV[First+Parent]);
    if (Parent == 0) { return; }
    Parent--;
  }
}