SNAP Library, Developer Reference  2012-10-02 12:56:23
SNAP, a general purpose network analysis and graph mining library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes
TGraphKey Class Reference

#include <ghash.h>

Collaboration diagram for TGraphKey:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 TGraphKey ()
 TGraphKey (const TSFltV &GraphSigV)
 TGraphKey (const TIntV &GraphSigV)
 TGraphKey (const TFltV &GraphSigV)
 TGraphKey (const TGraphKey &GraphKey)
 TGraphKey (TSIn &SIn)
void Save (TSOut &SOut) const
TGraphKey & operator= (const TGraphKey &GraphKey)
bool operator== (const TGraphKey &GraphKey) const
int GetPrimHashCd () const
int GetSecHashCd () const
int GetNodes () const
int GetEdges () const
int GetSigLen () const
int GetVariant () const
void SetVariant (const int &Variant)
void SetEdgeV (const TIntPrV &EdgeIdV)
PNGraph GetNGraph () const
void TakeGraph (const PNGraph &Graph)
void TakeGraph (const PNGraph &Graph, TIntPrV &NodeMap)
void TakeSig (const PNGraph &Graph, const int &MnSvdGraph, const int &MxSvdGraph)
void SaveTxt (FILE *F) const
void SaveGViz (const TStr &OutFNm, const TStr &Desc=TStr(), const TStr &NodeAttrs="", const int &Size=-1) const
void DrawGViz (const TStr &OutFNm, const TStr &Desc=TStr(), const TStr &NodeAttrs="", const int &Size=-1) const

Static Public Member Functions

static bool IsIsomorph (const TGraphKey &Key1, const TGraphKey &Key2, const TIntV &NodeIdMap)
static bool IsIsomorph (const TGraphKey &Key1, const TGraphKey &Key2, const TVec< TIntV > &NodeIdMapV)
static bool IsIsomorph (const TGraphKey &Key1, const TGraphKey &Key2, const TVec< TIntV > &NodeIdMapV, int &IsoPermId)

Public Attributes

TInt Nodes
TIntPrV EdgeV
TFltV SigV
TInt VariantId

Static Public Attributes

static const int RoundTo = 4

Detailed Description

Graph Hash Table Key.

Definition at line 3 of file ghash.h.

Constructor & Destructor Documentation

TGraphKey::TGraphKey ( ) [inline]

Definition at line 13 of file ghash.h.

: Nodes(-1), EdgeV(), SigV(), VariantId(0) { }
TGraphKey::TGraphKey ( const TSFltV &  GraphSigV)

Definition at line 5 of file ghash.cpp.

References TVec< TVal >::Gen(), TVec< TVal >::Len(), TMath::Round(), RoundTo, and SigV.

                                            : Nodes(-1), EdgeV(), SigV(), VariantId(0) {
  SigV.Gen(GraphSigV.Len());
  for (int i = 0; i < GraphSigV.Len(); i++) {
    SigV[i] = TFlt(TMath::Round(GraphSigV[i], RoundTo));
  }
}

Here is the call graph for this function:

TGraphKey::TGraphKey ( const TIntV &  GraphSigV)

Definition at line 12 of file ghash.cpp.

References TVec< TVal >::Gen(), TVec< TVal >::Len(), and SigV.

                                           : Nodes(-1), EdgeV(), SigV(), VariantId(0) {
  SigV.Gen(GraphSigV.Len());
  for (int i = 0; i < GraphSigV.Len(); i++) {
    SigV[i] = TFlt(GraphSigV[i]());
  }
}

Here is the call graph for this function:

TGraphKey::TGraphKey ( const TFltV &  GraphSigV)

Definition at line 19 of file ghash.cpp.

References TVec< TVal >::Gen(), TVec< TVal >::Len(), TMath::Round(), RoundTo, and SigV.

                                           : Nodes(-1), EdgeV(), SigV(), VariantId(0) {
  SigV.Gen(GraphSigV.Len());
  for (int i = 0; i < GraphSigV.Len(); i++) {
    SigV[i] = TFlt(TMath::Round(GraphSigV[i], RoundTo));
  }
}

Here is the call graph for this function:

TGraphKey::TGraphKey ( const TGraphKey &  GraphKey)

Definition at line 26 of file ghash.cpp.

                                              : Nodes(GraphKey.Nodes),
  EdgeV(GraphKey.EdgeV), SigV(GraphKey.SigV), VariantId(GraphKey.VariantId) {
}
TGraphKey::TGraphKey ( TSIn &  SIn)

Definition at line 30 of file ghash.cpp.

: Nodes(SIn), EdgeV(SIn), SigV(SIn), VariantId(SIn) { }

Member Function Documentation

void TGraphKey::DrawGViz ( const TStr &  OutFNm,
const TStr &  Desc = TStr(),
const TStr &  NodeAttrs = "",
const int &  Size = -1 
) const

Definition at line 179 of file ghash.cpp.

References TStr::GetFMid(), TSnap::TSnapDetail::GVizDoLayout(), gvlDot, and SaveGViz().

                                                                                                           {
  const TStr DotFNm = OutFNm.GetFMid()+".dot";
  SaveGViz(DotFNm, Desc, NodeAttrs, Size);
  TSnap::TSnapDetail::GVizDoLayout(DotFNm, OutFNm, gvlDot);
}

Here is the call graph for this function:

int TGraphKey::GetEdges ( ) const [inline]

Definition at line 27 of file ghash.h.

References EdgeV, and TVec< TVal >::Len().

Referenced by TGHash< TDat >::DrawGViz(), GetNGraph(), SaveGViz(), SaveTxt(), and TGHash< TDat >::SaveTxt().

{ return EdgeV.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

PNGraph TGraphKey::GetNGraph ( ) const

Definition at line 47 of file ghash.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::Defrag(), EdgeV, G(), GetEdges(), GetNodes(), and New().

                                   {
  PNGraph G = TNGraph::New();
  for (int i = 0; i < GetNodes(); i++) G->AddNode(i);
  for (int e = 0; e < GetEdges(); e++) {
    G->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2);
  }
  G->Defrag();
  return G;
}

Here is the call graph for this function:

int TGraphKey::GetNodes ( ) const [inline]

Definition at line 26 of file ghash.h.

References Nodes.

Referenced by TGHash< TDat >::AddKey(), TGHash< TDat >::DrawGViz(), GetNGraph(), TGHash< TDat >::IsGetKeyId(), SaveGViz(), SaveTxt(), and TGHash< TDat >::SaveTxt().

{ return Nodes; }

Here is the caller graph for this function:

int TGraphKey::GetPrimHashCd ( ) const [inline]

Definition at line 23 of file ghash.h.

References TVec< TVal >::GetPrimHashCd(), SigV, and VariantId.

{ return abs(SigV.GetPrimHashCd() ^ VariantId); }

Here is the call graph for this function:

int TGraphKey::GetSecHashCd ( ) const [inline]

Definition at line 24 of file ghash.h.

References TVec< TVal >::GetSecHashCd(), SigV, and VariantId.

{ return abs(SigV.GetSecHashCd() ^ VariantId<<8); }

Here is the call graph for this function:

int TGraphKey::GetSigLen ( ) const [inline]

Definition at line 28 of file ghash.h.

References TVec< TVal >::Len(), and SigV.

{ return SigV.Len(); }

Here is the call graph for this function:

int TGraphKey::GetVariant ( ) const [inline]

Definition at line 29 of file ghash.h.

References VariantId.

{ return VariantId; }
bool TGraphKey::IsIsomorph ( const TGraphKey &  Key1,
const TGraphKey &  Key2,
const TIntV &  NodeIdMap 
) [static]

Definition at line 185 of file ghash.cpp.

References EdgeV, TVec< TVal >::Len(), Nodes, and TVec< TVal >::SearchBin().

Referenced by TGHash< TDat >::AddKey(), TGHash< TDat >::GetNodeMap(), TGHash< TDat >::IsGetKeyId(), and IsIsomorph().

                                                                                               {
  const TIntPrV& EdgeV1 = Key1.EdgeV;
  const TIntPrV& EdgeV2 = Key2.EdgeV;
  if (Key1.Nodes != Key2.Nodes || EdgeV1.Len() != EdgeV2.Len()) return false;
  for (int e1 = 0; e1 < EdgeV1.Len(); e1++) {
    const TIntPr Edge2(NodeIdMap[EdgeV1[e1].Val1], NodeIdMap[EdgeV1[e1].Val2]);
    if (EdgeV2.SearchBin(Edge2) == -1) return false;
  }
  return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

bool TGraphKey::IsIsomorph ( const TGraphKey &  Key1,
const TGraphKey &  Key2,
const TVec< TIntV > &  NodeIdMapV 
) [static]

Definition at line 196 of file ghash.cpp.

References IsIsomorph().

                                                                                                      {
  int IsoPermId;
  return IsIsomorph(Key1, Key2, NodeIdMapV, IsoPermId);
}

Here is the call graph for this function:

bool TGraphKey::IsIsomorph ( const TGraphKey &  Key1,
const TGraphKey &  Key2,
const TVec< TIntV > &  NodeIdMapV,
int &  IsoPermId 
) [static]

Definition at line 201 of file ghash.cpp.

References EdgeV, TVec< TVal >::Len(), and Nodes.

                                                                                                                      {
  const TIntPrV& EdgeV1 = Key1.EdgeV;
  const TIntPrV& EdgeV2 = Key2.EdgeV;
  //for (int i = 0; i < EdgeV1.Len(); i++) printf("\t%d - %d\n", EdgeV1[i].Val1, EdgeV1[i].Val2);  printf("\n");
  //for (int i = 0; i < EdgeV2.Len(); i++) printf("\t%d - %d\n", EdgeV2[i].Val1, EdgeV2[i].Val2);
  if (Key1.Nodes != Key2.Nodes || EdgeV1.Len() != EdgeV2.Len()) return false;
  const int Nodes = NodeIdMapV[0].Len();
  // fast adjecency matrix
  TIntV AdjMtx2(Nodes*Nodes);
  for (int i = 0; i < EdgeV2.Len(); i++) {
    AdjMtx2[EdgeV2[i].Val1*Nodes + EdgeV2[i].Val2] = 1;
  }
  for (int perm = 0; perm < NodeIdMapV.Len(); perm++) {
    const TIntV& NodeIdMap = NodeIdMapV[perm];
    bool IsIso = true;
    for (int e1 = 0; e1 < EdgeV1.Len(); e1++) {
      const int NId1 = NodeIdMap[EdgeV1[e1].Val1];
      const int NId2 = NodeIdMap[EdgeV1[e1].Val2];
      if (AdjMtx2[NId1*Nodes + NId2] != 1) {
        IsIso = false;  break; }
    }
    if (IsIso) {
      IsoPermId = perm;
      return true; }
  }
  IsoPermId = -1;
  return false;
}

Here is the call graph for this function:

TGraphKey & TGraphKey::operator= ( const TGraphKey &  GraphKey)

Definition at line 37 of file ghash.cpp.

References EdgeV, Nodes, SigV, and VariantId.

                                                           {
  if (this != &GraphKey) {
    Nodes = GraphKey.Nodes;
    EdgeV = GraphKey.EdgeV;
    SigV = GraphKey.SigV;
    VariantId = GraphKey.VariantId;
  }
  return *this;
}
bool TGraphKey::operator== ( const TGraphKey &  GraphKey) const [inline]

Definition at line 21 of file ghash.h.

References SigV, and VariantId.

{ return SigV==GraphKey.SigV && VariantId==GraphKey.VariantId; }
void TGraphKey::Save ( TSOut &  SOut) const

Definition at line 32 of file ghash.cpp.

References EdgeV, Nodes, TVec< TVal >::Save(), TInt::Save(), SigV, and VariantId.

                                      {
  Nodes.Save(SOut);  EdgeV.Save(SOut);
  SigV.Save(SOut);  VariantId.Save(SOut);
}

Here is the call graph for this function:

void TGraphKey::SaveGViz ( const TStr &  OutFNm,
const TStr &  Desc = TStr(),
const TStr &  NodeAttrs = "",
const int &  Size = -1 
) const

Definition at line 153 of file ghash.cpp.

References TStr::CStr(), EdgeV, TVec< TVal >::Empty(), TStr::Empty(), F(), GetEdges(), GetNodes(), TVec< TVal >::Len(), and Nodes.

Referenced by DrawGViz(), and TGHash< TDat >::DrawGViz().

                                                                                                           {
  FILE *F = fopen(OutFNm.CStr(), "wt");
  fprintf(F, "/*****\n");
  fprintf(F, "  Graph (%d, %d)\n", GetNodes(), GetEdges());
  //if (! Desc.Empty()) fprintf(F, "  %s\n", Desc.CStr());
  fprintf(F, "*****/\n\n");
  fprintf(F, "digraph G {\n");
  if (Size != -1) fprintf(F, "  size=\"%d,%d\";\n", Size, Size);
  fprintf(F, "  graph [splines=true overlap=false]\n"); //size=\"12,10\" ratio=fill
  if (NodeAttrs.Empty()) fprintf(F, "  node  [shape=ellipse, width=0.3, height=0.3]\n");
  else fprintf(F, "  node  [shape=ellipse, %s]\n", NodeAttrs.CStr());
  if (! EdgeV.Empty()) {
    for (int e = 0; e < EdgeV.Len(); e++) {
      fprintf(F, "  %d -> %d;\n", EdgeV[e].Val1(), EdgeV[e].Val2()); }
  } else {
    for (int n = 0; n < Nodes; n++) { fprintf(F, "  %d;\n", n); }
  }
  if (! Desc.Empty()) {
    fprintf(F, "  label = \"\\n%s\\n\";", Desc.CStr());
    fprintf(F, "  fontsize=24;\n");
  }
  fprintf(F, "}\n");
  fclose(F);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphKey::SaveTxt ( FILE *  F) const

Definition at line 146 of file ghash.cpp.

References EdgeV, GetEdges(), GetNodes(), and TVec< TVal >::Len().

                                     {
  fprintf(F, "nodes: %d.  edges: %d\n", GetNodes(), GetEdges());
  for (int i = 0; i < EdgeV.Len(); i++) {
    fprintf(F,"  %d\t%d\n", EdgeV[i].Val1(), EdgeV[i].Val2());
  }
}

Here is the call graph for this function:

void TGraphKey::SetEdgeV ( const TIntPrV &  EdgeIdV) [inline]

Definition at line 31 of file ghash.h.

References EdgeV.

{ EdgeV = EdgeIdV; }
void TGraphKey::SetVariant ( const int &  Variant) [inline]

Definition at line 30 of file ghash.h.

References VariantId.

Referenced by TGHash< TDat >::AddKey(), TGHash< TDat >::GetNodeMap(), and TGHash< TDat >::IsGetKeyId().

{ VariantId = Variant; }

Here is the caller graph for this function:

void TGraphKey::TakeGraph ( const PNGraph &  Graph)

Definition at line 58 of file ghash.cpp.

References TVec< TVal >::Add(), THash< TKey, TDat, THashFunc >::AddKey(), TNGraph::BegNI(), EdgeV, TNGraph::EndNI(), TVec< TVal >::Gen(), THash< TKey, TDat, THashFunc >::GetKeyId(), TNGraph::GetNodes(), Nodes, TVec< TVal >::Pack(), and TVec< TVal >::Sort().

Referenced by TGHash< TDat >::AddKey(), TGHash< TDat >::GetNodeMap(), and TGHash< TDat >::IsGetKeyId().

                                              {
  TIntH NodeIdH;
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    NodeIdH.AddKey(NI.GetId()); }
  Nodes = Graph->GetNodes();
  EdgeV.Gen(Nodes, 0);
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    const int NewNId = NodeIdH.GetKeyId(NI.GetId());
    for (int i = 0; i < NI.GetOutDeg(); i++) {
      EdgeV.Add(TIntPr(NewNId, NodeIdH.GetKeyId(NI.GetOutNId(i))));
    }
  }
  EdgeV.Sort(true);
  EdgeV.Pack();
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphKey::TakeGraph ( const PNGraph &  Graph,
TIntPrV &  NodeMap 
)

Definition at line 74 of file ghash.cpp.

References TVec< TVal >::Add(), THashSet< TKey, THashFunc >::AddKey(), TNGraph::BegNI(), EdgeV, TNGraph::EndNI(), TVec< TVal >::Gen(), THashSet< TKey, THashFunc >::GetKeyId(), TNGraph::GetNodes(), Nodes, TVec< TVal >::Pack(), and TVec< TVal >::Sort().

                                                                {
  TIntSet NodeIdH;
  int n = 0;
  NodeMap.Gen(Graph->GetNodes(), 0);
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, n++) {
    NodeIdH.AddKey(NI.GetId());
    NodeMap.Add(TIntPr(NI.GetId(), n));
  }
  Nodes = Graph->GetNodes();
  EdgeV.Gen(Nodes, 0);
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    const int NewNId = NodeIdH.GetKeyId(NI.GetId());
    for (int i = 0; i < NI.GetOutDeg(); i++) {
      EdgeV.Add(TIntPr(NewNId, NodeIdH.GetKeyId(NI.GetOutNId(i))));
    }
  }
  EdgeV.Sort(true);
  EdgeV.Pack();
}

Here is the call graph for this function:

void TGraphKey::TakeSig ( const PNGraph &  Graph,
const int &  MnSvdGraph,
const int &  MxSvdGraph 
)

Definition at line 94 of file ghash.cpp.

References TVec< TVal >::Add(), THash< TKey, TDat, THashFunc >::AddKey(), TVVec< TVal >::At(), TNGraph::BegNI(), TNGraph::EndNI(), TVec< TVal >::Gen(), TNGraph::GetEdges(), THash< TKey, TDat, THashFunc >::GetKeyId(), TNGraph::GetNodes(), TVec< TVal >::Len(), Nodes, TVec< TVal >::Pack(), TMath::Round(), RoundTo, SigV, TVec< TVal >::Sort(), Svd(), and VariantId.

Referenced by TGHash< TDat >::AddKey(), TGHash< TDat >::GetNodeMap(), and TGHash< TDat >::IsGetKeyId().

                                                                                          {
  const int Edges = Graph->GetEdges();
  Nodes = Graph->GetNodes();
  VariantId = 0;
  SigV.Gen(2+Nodes, 0);
  // degree sequence
  TIntPrV DegV(Nodes, 0);
  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
    DegV.Add(TIntPr(NodeI.GetInDeg(), NodeI.GetOutDeg()));
  }
  DegV.Sort(false);
  SigV.Add(TFlt(Nodes));
  SigV.Add(TFlt(Edges));
  for (int i = 0; i < DegV.Len(); i++) {
    SigV.Add(DegV[i].Val1());
    SigV.Add(DegV[i].Val2());
  }
  // singular values signature
  //   it turns out that it is cheaper to do brute force isomorphism
  //   checking than to calculate SVD and then check isomorphism
  if (Nodes >= MnSvdGraph && Nodes < MxSvdGraph) {
    // perform full SVD
    TFltVV AdjMtx(Nodes+1, Nodes+1);
    TFltV SngValV;
    TFltVV LSingV, RSingV;
    TIntH NodeIdH;
    // create adjecency matrix
    for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
      NodeIdH.AddKey(NodeI.GetId());
    }
    for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
      const int NodeId = NodeIdH.GetKeyId(NodeI.GetId()) + 1;
      for (int e = 0; e < NodeI.GetOutDeg(); e++) {
        const int DstNId = NodeIdH.GetKeyId(NodeI.GetOutNId(e)) + 1;  // no self edges
        if (NodeId != DstNId) AdjMtx.At(NodeId, DstNId) = 1;
      }
    }
    try { // can fail to converge but results seem to be good
      TSvd::Svd(AdjMtx, LSingV, SngValV, RSingV);
    } catch(...) {
      printf("\n***No SVD convergence: G(%d, %d): SngValV.Len():%d\n", Nodes(), Graph->GetEdges(), SngValV.Len());
    }
    // round singular values
    SngValV.Sort(false);
    for (int i = 0; i < SngValV.Len(); i++) {
      SigV.Add(TMath::Round(SngValV[i], RoundTo));
    }
  }
  //printf("SIG:\n");  for (int i = 0; i < SigV.Len(); i++) { printf("\t%f\n", SigV[i]); }
  SigV.Pack();
}

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

TIntPrV TGraphKey::EdgeV

Definition at line 9 of file ghash.h.

Referenced by GetEdges(), GetNGraph(), IsIsomorph(), operator=(), Save(), SaveGViz(), SaveTxt(), SetEdgeV(), and TakeGraph().

TInt TGraphKey::Nodes

Definition at line 8 of file ghash.h.

Referenced by GetNodes(), IsIsomorph(), operator=(), Save(), SaveGViz(), TakeGraph(), and TakeSig().

const int TGraphKey::RoundTo = 4 [static]

Definition at line 5 of file ghash.h.

Referenced by TakeSig(), and TGraphKey().

TFltV TGraphKey::SigV

Definition at line 10 of file ghash.h.

Referenced by GetPrimHashCd(), GetSecHashCd(), GetSigLen(), operator=(), operator==(), Save(), TakeSig(), and TGraphKey().

TInt TGraphKey::VariantId

Definition at line 11 of file ghash.h.

Referenced by GetPrimHashCd(), GetSecHashCd(), GetVariant(), operator=(), operator==(), Save(), SetVariant(), and TakeSig().

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