SNAP Library 2.2, Developer Reference  2014-03-11 19:15:55
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
Static Public Member Functions
TCesnaUtil Class Reference

#include <agmattr.h>

List of all members.

Static Public Member Functions

template<class PGraph >
static double GetConductance (const PGraph &Graph, const TIntSet &CmtyS, const int Edges)
template<class PGraph >
static void GenHoldOutPairs (const PGraph &G, TVec< TIntSet > &HoldOutSet, double HOFrac, TRnd &Rnd)
template<class PGraph >
static void GetNbhCom (const PGraph &Graph, const int NID, TIntSet &NBCmtyS)
template<class PGraph >
static void GetNIdPhiV (const PGraph &G, TFltIntPrV &NIdPhiV)
static void LoadNIDAttrHFromNIDKH (const TIntV &NIDV, const TStr &InFNm, THash< TInt, TIntV > &NIDAttrH, const TStrHash< TInt > &NodeNameH, const TSsFmt Sep=ssfTabSep)
static void LoadNIDAttrHFromNIDKH (const TIntV &NIDV, const TStr &InFNm, THash< TInt, TIntV > &NIDAttrH)
static void DumpNIDAttrHToNIDK (const TStr &FNm, const THash< TInt, TIntSet > &NIDAttrH, const TStrHash< TInt > &FeatNameH, const TStrHash< TInt > &NodeNameH)
static void DumpNIDAttrHToNIDK (const TStr &FNm, const THash< TInt, TIntSet > &NIDAttrH, const TStrHash< TInt > &FeatNameH)
static void DumpNIDAttrHToNIDK (const TStr &FNm, const THash< TInt, TIntSet > &NIDAttrH)
static void DumpNIDAttrHToNIDK (const TStr &FNm, const THash< TInt, TIntV > &NIDAttrH, const TStrHash< TInt > &FeatNameH, const TStrHash< TInt > &NodeNameH)
static void DumpNIDAttrHToNIDK (const TStr &FNm, const THash< TInt, TIntV > &NIDAttrH, const TStrHash< TInt > &FeatNameH)
static void DumpNIDAttrHToNIDK (const TStr &FNm, const THash< TInt, TIntV > &NIDAttrH)
static int GetAttrs (const THash< TInt, TIntV > &NIDAttrH)
static void DumpNIDAttrHToMetis (const TStr &FNm, const THash< TInt, TIntV > &NIDAttrH, const TIntV &NIDV)
static void FilterLowEntropy (const THash< TInt, TIntV > &OldNIDAttrH, THash< TInt, TIntV > &NewNIDAttrH, const TIntStrH &OldNameH, TIntStrH &NewNameH, const double MinFrac=0.00001, const double MaxFrac=0.95, const int MinCnt=3)
static void FilterLowEntropy (const THash< TInt, TIntV > &OldNIDAttrH, THash< TInt, TIntV > &NewNIDAttrH, const double MinFrac=0.00001, const double MaxFrac=0.95, const int MinCnt=3)

Detailed Description

Definition at line 5 of file agmattr.h.

Member Function Documentation

static void TCesnaUtil::DumpNIDAttrHToMetis ( const TStr &  FNm,
const THash< TInt, TIntV > &  NIDAttrH,
const TIntV &  NIDV 
) [inline, static]

Definition at line 176 of file agmattr.h.

References TStr::CStr(), THash< TKey, TDat, THashFunc >::GetDat(), IAssert, THash< TKey, TDat, THashFunc >::IsKey(), and TVec< TVal, TSizeTy >::Len().

                                                                                                          {
    int AttrCnt = 0;
    for (int u = 1; u < NIDV.Len(); u++) {
      if (! NIDAttrH.IsKey(NIDV[u])) { continue; }
      AttrCnt += NIDAttrH.GetDat(NIDV[u]).Len();
    }
    IAssert (NIDV[0] == -1);
    FILE* F = fopen(FNm.CStr(), "wt");
    fprintf(F, "%d %d\n", NIDV.Len() - 1, AttrCnt);
    int TmpCnt = 0;
    for (int u = 1; u < NIDV.Len(); u++) {
      if (NIDAttrH.IsKey(NIDV[u])) {  
        for (int k = 0; k < NIDAttrH.GetDat(NIDV[u]).Len(); k++) {
          if (k > 0) { fprintf(F, " "); }
          fprintf(F, "%d", NIDAttrH.GetDat(NIDV[u])[k].Val + 1);
          TmpCnt++;
        }
      }
      fprintf(F, "\n");
    }
    fclose(F);
    IAssert(AttrCnt == TmpCnt);

  }

Here is the call graph for this function:

static void TCesnaUtil::DumpNIDAttrHToNIDK ( const TStr &  FNm,
const THash< TInt, TIntSet > &  NIDAttrH,
const TStrHash< TInt > &  FeatNameH,
const TStrHash< TInt > &  NodeNameH 
) [inline, static]

Definition at line 124 of file agmattr.h.

References TStr::CStr(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::GetKey(), TStrHash< TDat, TStringPool, THashFunc >::GetKey(), TStrHash< TDat, TStringPool, THashFunc >::IsKeyId(), and THash< TKey, TDat, THashFunc >::Len().

Referenced by DumpNIDAttrHToNIDK().

                                                                                                                                                          {
    FILE* F = fopen(FNm.CStr(), "wt");
    for (int u = 0; u < NIDAttrH.Len(); u++) {
      int NID = NIDAttrH.GetKey(u);
      TStr NodeName = NodeNameH.IsKeyId(NID)? NodeNameH.GetKey(NID): TStr::Fmt("%d", NID);
      for (int k = 0; k < NIDAttrH[u].Len(); k++) {
        int KID = NIDAttrH[u][k];
        TStr FeatName = FeatNameH.IsKeyId(KID)? FeatNameH.GetKey(KID): TStr::Fmt("%d", KID);
        fprintf(F,"%s\t%s\n", NodeName.CStr(), FeatName.CStr());
      }
    }
    fclose(F);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

static void TCesnaUtil::DumpNIDAttrHToNIDK ( const TStr &  FNm,
const THash< TInt, TIntSet > &  NIDAttrH,
const TStrHash< TInt > &  FeatNameH 
) [inline, static]

Definition at line 137 of file agmattr.h.

References DumpNIDAttrHToNIDK().

                                                                                                                         {
    TStrHash<TInt> TmpH;
    DumpNIDAttrHToNIDK(FNm, NIDAttrH, FeatNameH, TmpH);
  }

Here is the call graph for this function:

static void TCesnaUtil::DumpNIDAttrHToNIDK ( const TStr &  FNm,
const THash< TInt, TIntSet > &  NIDAttrH 
) [inline, static]

Definition at line 141 of file agmattr.h.

References DumpNIDAttrHToNIDK().

                                                                                        {
    TStrHash<TInt> TmpH1, TmpH2;
    DumpNIDAttrHToNIDK(FNm, NIDAttrH, TmpH1, TmpH2);
  }

Here is the call graph for this function:

static void TCesnaUtil::DumpNIDAttrHToNIDK ( const TStr &  FNm,
const THash< TInt, TIntV > &  NIDAttrH,
const TStrHash< TInt > &  FeatNameH,
const TStrHash< TInt > &  NodeNameH 
) [inline, static]

Definition at line 145 of file agmattr.h.

References TStr::CStr(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::GetKey(), TStrHash< TDat, TStringPool, THashFunc >::GetKey(), TStrHash< TDat, TStringPool, THashFunc >::IsKeyId(), and THash< TKey, TDat, THashFunc >::Len().

                                                                                                                                                        {
    FILE* F = fopen(FNm.CStr(), "wt");
    for (int u = 0; u < NIDAttrH.Len(); u++) {
      int NID = NIDAttrH.GetKey(u);
      TStr NodeName = NodeNameH.IsKeyId(NID)? NodeNameH.GetKey(NID): TStr::Fmt("%d", NID);
      for (int k = 0; k < NIDAttrH[u].Len(); k++) {
        int KID = NIDAttrH[u][k];
        TStr FeatName = FeatNameH.IsKeyId(KID)? FeatNameH.GetKey(KID): TStr::Fmt("%d", KID);
        fprintf(F,"%s\t%s\n", NodeName.CStr(), FeatName.CStr());
      }
    }
    fclose(F);
  }

Here is the call graph for this function:

static void TCesnaUtil::DumpNIDAttrHToNIDK ( const TStr &  FNm,
const THash< TInt, TIntV > &  NIDAttrH,
const TStrHash< TInt > &  FeatNameH 
) [inline, static]

Definition at line 158 of file agmattr.h.

References DumpNIDAttrHToNIDK().

                                                                                                                       {
    TStrHash<TInt> TmpH;
    DumpNIDAttrHToNIDK(FNm, NIDAttrH, FeatNameH, TmpH);
  }

Here is the call graph for this function:

static void TCesnaUtil::DumpNIDAttrHToNIDK ( const TStr &  FNm,
const THash< TInt, TIntV > &  NIDAttrH 
) [inline, static]

Definition at line 162 of file agmattr.h.

References DumpNIDAttrHToNIDK().

                                                                                      {
    TStrHash<TInt> TmpH1, TmpH2;
    DumpNIDAttrHToNIDK(FNm, NIDAttrH, TmpH1, TmpH2);
  }

Here is the call graph for this function:

static void TCesnaUtil::FilterLowEntropy ( const THash< TInt, TIntV > &  OldNIDAttrH,
THash< TInt, TIntV > &  NewNIDAttrH,
const TIntStrH &  OldNameH,
TIntStrH &  NewNameH,
const double  MinFrac = 0.00001,
const double  MaxFrac = 0.95,
const int  MinCnt = 3 
) [inline, static]

Definition at line 200 of file agmattr.h.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Empty(), THash< TKey, TDat, THashFunc >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), and THash< TKey, TDat, THashFunc >::SortByDat().

Referenced by FilterLowEntropy().

                                                                                                                                                                                                                                        {
    TIntH KIDCntH;
    for (int u = 0; u < OldNIDAttrH.Len(); u++) {
      for (int k = 0; k < OldNIDAttrH[u].Len(); k++) {
        KIDCntH.AddDat(OldNIDAttrH[u][k])++;
      }
    }
    KIDCntH.SortByDat(false);

    TIntSet SelectedK(KIDCntH.Len());
    for (int c = 0; c < KIDCntH.Len(); c++) {
      double Frac = (double) KIDCntH[c].Val / (double) OldNIDAttrH.Len();
      if (KIDCntH[c].Val < MinCnt) { continue; }
      if (Frac > MaxFrac || Frac < MinFrac) { continue; }
      SelectedK.AddKey(KIDCntH.GetKey(c));
    }
    printf("%d attributes selected from %d\n", SelectedK.Len(), KIDCntH.Len());
    NewNIDAttrH.Gen(OldNIDAttrH.Len());
    for (int u = 0; u < OldNIDAttrH.Len(); u++) {
      int NID = OldNIDAttrH.GetKey(u);
      TIntV& AttrV = NewNIDAttrH.AddDat(NID);
      for (int k = 0; k < OldNIDAttrH[u].Len(); k++) {
        if (! SelectedK.IsKey(OldNIDAttrH[u][k])) { continue; }
        AttrV.Add(SelectedK.GetKeyId(OldNIDAttrH[u][k]));
      }
    }

    if (! OldNameH.Empty()) {
      NewNameH.Gen(SelectedK.Len());
      for (int k = 0; k < SelectedK.Len(); k++) {
        int OldKID = SelectedK.GetKey(k);
        if (OldNameH.IsKey(OldKID)) {
          NewNameH.AddDat(k, OldNameH.GetDat(OldKID));
        }
      }
      printf("%d attributes names copied\n", NewNameH.Len());
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

static void TCesnaUtil::FilterLowEntropy ( const THash< TInt, TIntV > &  OldNIDAttrH,
THash< TInt, TIntV > &  NewNIDAttrH,
const double  MinFrac = 0.00001,
const double  MaxFrac = 0.95,
const int  MinCnt = 3 
) [inline, static]

Definition at line 238 of file agmattr.h.

References FilterLowEntropy().

                                                                                                                                                                                          {
    TIntStrH TmpH1, TmpH2;
    FilterLowEntropy(OldNIDAttrH, NewNIDAttrH, TmpH1, TmpH2, MinFrac, MaxFrac, MinCnt);
  }

Here is the call graph for this function:

template<class PGraph >
static void TCesnaUtil::GenHoldOutPairs ( const PGraph &  G,
TVec< TIntSet > &  HoldOutSet,
double  HOFrac,
TRnd &  Rnd 
) [inline, static]

Definition at line 38 of file agmattr.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), TRnd::GetUniDevInt(), gfDirected, HasGraphFlag, and TMath::Round().

Referenced by TCesna::FindComs(), and TCesna::SetHoldOut().

                                                                                                     {
    TIntPrV EdgeV(G->GetEdges(), 0);
    for (typename PGraph::TObj::TEdgeI EI = G->BegEI(); EI < G->EndEI(); EI++) {
      EdgeV.Add(TIntPr(EI.GetSrcNId(), EI.GetDstNId()));
    }
    EdgeV.Shuffle(Rnd);

    const bool GraphType = HasGraphFlag(typename PGraph::TObj, gfDirected);
    HoldOutSet.Gen(G->GetNodes());
    int HOTotal = int(HOFrac * G->GetNodes() * (G->GetNodes() - 1) / 2.0);
    if (GraphType) { HOTotal *= 2;}
    int HOCnt = 0;
    int HOEdges = (int) TMath::Round(HOFrac * G->GetEdges());
    printf("holding out %d edges...\n", HOEdges);
    for (int he = 0; he < (int) HOEdges; he++) {
      HoldOutSet[EdgeV[he].Val1].AddKey(EdgeV[he].Val2);
      if (! GraphType) { HoldOutSet[EdgeV[he].Val2].AddKey(EdgeV[he].Val1); }
      HOCnt++;
    }
    printf("%d Edges hold out\n", HOCnt);
    while(HOCnt++ < HOTotal) {
      int SrcNID = Rnd.GetUniDevInt(G->GetNodes());
      int DstNID = Rnd.GetUniDevInt(G->GetNodes());
      if (SrcNID == DstNID) { continue; }
      HoldOutSet[SrcNID].AddKey(DstNID);
      if (! GraphType) { HoldOutSet[DstNID].AddKey(SrcNID); }
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

static int TCesnaUtil::GetAttrs ( const THash< TInt, TIntV > &  NIDAttrH) [inline, static]

Definition at line 166 of file agmattr.h.

References THash< TKey, TDat, THashFunc >::Len().

                                                          {
    int Attrs = 0;
    for (int u = 0; u < NIDAttrH.Len(); u++) {
      for (int k = 0; k < NIDAttrH[u].Len(); k++) {
        if (NIDAttrH[u][k] >= Attrs) { Attrs = NIDAttrH[u][k] + 1; }
      }
    }
    return Attrs;
  }

Here is the call graph for this function:

template<class PGraph >
static double TCesnaUtil::GetConductance ( const PGraph &  Graph,
const TIntSet &  CmtyS,
const int  Edges 
) [inline, static]

Definition at line 10 of file agmattr.h.

References gfDirected, HasGraphFlag, THashSet< TKey, THashFunc >::IsKey(), and THashSet< TKey, THashFunc >::Len().

Referenced by GetNIdPhiV().

                                                                                         {
  const bool GraphType = HasGraphFlag(typename PGraph::TObj, gfDirected);
  int Edges2;
  if (GraphType) { Edges2 = Edges >= 0 ? Edges : Graph->GetEdges(); }
  else { Edges2 = Edges >= 0 ? 2 * Edges : Graph->GetEdges(); }
  int Vol = 0,  Cut = 0; 
  double Phi = 0.0;
  for (int i = 0; i < CmtyS.Len(); i++) {
    if (! Graph->IsNode(CmtyS[i])) { continue; }
    typename PGraph::TObj::TNodeI  NI = Graph->GetNI(CmtyS[i]);
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (! CmtyS.IsKey(NI.GetOutNId(e))) { Cut += 1; }
    }
    Vol += NI.GetOutDeg();
  }
  // get conductance
  if (Vol != Edges2) {
    if (2 * Vol > Edges2) { Phi = Cut / double (Edges2 - Vol); }
    else if (Vol == 0) { Phi = 0.0; }
    else { Phi = Cut / double(Vol); }
  } else {
    if (Vol == Edges2) { Phi = 1.0; }
  }
  return Phi;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >
static void TCesnaUtil::GetNbhCom ( const PGraph &  Graph,
const int  NID,
TIntSet &  NBCmtyS 
) [inline, static]

Definition at line 68 of file agmattr.h.

References THashSet< TKey, THashFunc >::AddKey(), and THashSet< TKey, THashFunc >::Gen().

                                                                              {
    typename PGraph::TObj::TNodeI NI = Graph->GetNI(NID);
    NBCmtyS.Gen(NI.GetDeg());
    NBCmtyS.AddKey(NID);
    for (int e = 0; e < NI.GetDeg(); e++) {
      NBCmtyS.AddKey(NI.GetNbrNId(e));
    }
  }

Here is the call graph for this function:

template<class PGraph >
static void TCesnaUtil::GetNIdPhiV ( const PGraph &  G,
TFltIntPrV &  NIdPhiV 
) [inline, static]

Definition at line 77 of file agmattr.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), GetConductance(), and TExeTm::GetTmStr().

                                                               {
    NIdPhiV.Gen(G->GetNodes(), 0);
    const int Edges = G->GetEdges();
    TExeTm RunTm;
    //compute conductance of neighborhood community
    for (typename PGraph::TObj::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI++) {
      TIntSet NBCmty(NI.GetDeg() + 1);
      double Phi;
      if (NI.GetDeg() < 5) { //do not include nodes with too few degree
        Phi = 1.0; 
      } else {
        TCesnaUtil::GetNbhCom<PGraph>(G, NI.GetId(), NBCmty);
        //if (NBCmty.Len() != NI.GetDeg() + 1) { printf("NbCom:%d, Deg:%d\n", NBCmty.Len(), NI.GetDeg()); }
        //IAssert(NBCmty.Len() == NI.GetDeg() + 1);
        Phi = TCesnaUtil::GetConductance(G, NBCmty, Edges);
      }
      //NCPhiH.AddDat(u, Phi);
      NIdPhiV.Add(TFltIntPr(Phi, NI.GetId()));
    }
    printf("conductance computation completed [%s]\n", RunTm.GetTmStr());
    fflush(stdout);
  }

Here is the call graph for this function:

static void TCesnaUtil::LoadNIDAttrHFromNIDKH ( const TIntV &  NIDV,
const TStr &  InFNm,
THash< TInt, TIntV > &  NIDAttrH,
const TStrHash< TInt > &  NodeNameH,
const TSsFmt  Sep = ssfTabSep 
) [inline, static]

Definition at line 100 of file agmattr.h.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Clr(), TStr::CStr(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::Gen(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), TSsParser::GetFld(), TSsParser::GetInt(), TStr::GetInt(), TStrHash< TDat, TStringPool, THashFunc >::GetKeyId(), TSsParser::GetLineNo(), TUInt64::GetStr(), IAssertR, TVec< TVal, TSizeTy >::IsIn(), THash< TKey, TDat, THashFunc >::IsKey(), TStrHash< TDat, TStringPool, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TStrHash< TDat, TStringPool, THashFunc >::Len(), TSsParser::Next(), ssfTabSep, and TInt::Val.

Referenced by LoadNIDAttrHFromNIDKH().

                                                                                                                                                                       {
    NIDAttrH.Clr();
    NIDAttrH.Gen(NIDV.Len());
    for (int u = 0; u < NIDV.Len(); u++) { NIDAttrH.AddDat(NIDV[u]).Gen(0, 0); }
    TSsParser Ss(InFNm, ssfTabSep);
    while (Ss.Next()) {
      TStr NodeName = Ss.GetFld(0);
      TInt NID = NodeName.GetInt();
      if (NodeNameH.Len() > 0 && ! NodeNameH.IsKey(NodeName)) { continue; }
      if (NodeNameH.Len() > 0) { 
        IAssertR(NodeNameH.IsKey(NodeName), TStr::Fmt("NodeName:%s", NodeName.CStr())); 
        NID = NodeNameH.GetKeyId(NodeName);
      }
      if (! NIDAttrH.IsKey(NID)) { continue; } //ignore nodes who are not in the graph
      IAssertR(! NIDAttrH.GetDat(NID).IsIn(Ss.GetInt(1)), TStr::Fmt("NIdx:%d NID:%s, K:%d", NID.Val, NodeName.CStr(), Ss.GetInt(1)));
      NIDAttrH.GetDat(NID).Add(Ss.GetInt(1));
    }
    printf("%s nodes, %s lines read \n",  TUInt64::GetStr(NIDAttrH.Len()).CStr(), TUInt64::GetStr(Ss.GetLineNo()).CStr());
    //printf("%d nodes, %d lines read \n",  NIDAttrH.Len(), Ss.GetLineNo());
  }

Here is the call graph for this function:

Here is the caller graph for this function:

static void TCesnaUtil::LoadNIDAttrHFromNIDKH ( const TIntV &  NIDV,
const TStr &  InFNm,
THash< TInt, TIntV > &  NIDAttrH 
) [inline, static]

Definition at line 120 of file agmattr.h.

References LoadNIDAttrHFromNIDKH().

                                                                                                        {
    TStrHash<TInt> TmpH;
    LoadNIDAttrHFromNIDKH(NIDV, InFNm, NIDAttrH, TmpH);
  }

Here is the call graph for this function:

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