SNAP Library 2.1, User Reference  2013-09-25 10:47:25
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
TGraphKey Class Reference

Small Directed Graphs. More...

#include <ghash.h>

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
TGraphKeyoperator= (const TGraphKey &GraphKey)
bool operator== (const TGraphKey &GraphKey) const
int GetPrimHashCd () const
int GetSecHashCd () const
int GetNodes () const
 Returns the number of nodes in the graph.
int GetEdges () const
 Returns the number of edges in the graph.
int GetSigLen () const
 Returns the length of the signature vector of a graph.
int GetVariant () const
 Returns the graph variant Id.
void SetVariant (const int &Variant)
 Sets the Variant Id of a given graph.
void SetEdgeV (const TIntPrV &EdgeIdV)
 Returns a vector of directed edges of a graph.
PNGraph GetNGraph () const
 Returns the directed graph stored in the GraphKey object.
void TakeGraph (const PNGraph &Graph)
 Creates a key from a given directed graph.
void TakeGraph (const PNGraph &Graph, TIntPrV &NodeMap)
 Creates a key from a given directed graph.
void TakeSig (const PNGraph &Graph, const int &MnSvdGraph, const int &MxSvdGraph)
 Creates a signature for a given directed graph.
void SaveTxt (FILE *F) const
 Saves the graph as a list of edges.
void SaveGViz (const TStr &OutFNm, const TStr &Desc=TStr(), const TStr &NodeAttrs="", const int &Size=-1) const
 Saves the graph to the .DOT file format used by GraphViz.
void DrawGViz (const TStr &OutFNm, const TStr &Desc=TStr(), const TStr &NodeAttrs="", const int &Size=-1) const
 Saves the graph to the .DOT file format and calls GraphViz to draw it.

Static Public Member Functions

static bool IsIsomorph (const TGraphKey &Key1, const TGraphKey &Key2, const TIntV &NodeIdMap)
 Checks whether directed graph Key1 is isomorphic to the directed graph Key2 under node Id permutation NodeIdMap.
static bool IsIsomorph (const TGraphKey &Key1, const TGraphKey &Key2, const TVec< TIntV > &NodeIdMapV)
 Checks whether directed graph Key1 is isomorphic to the directed graph Key2 under all the permutations of node Ids stored in NodeIdMapV.
static bool IsIsomorph (const TGraphKey &Key1, const TGraphKey &Key2, const TVec< TIntV > &NodeIdMapV, int &IsoPermId)
 Checks whether directed graph Key1 is isomorphic to the directed graph Key2 under all the permutations of node Ids stored in NodeIdMapV and returns the Id of the permutation of node Ids (IsoPermId) which makes the two graphs isomorphic.

Public Attributes

TInt Nodes
TIntPrV EdgeV
TFltV SigV
TInt VariantId

Static Public Attributes

static const int RoundTo = 4

Detailed Description

Small Directed Graphs.

These graphs are used as keys of the TGHash graph hash table. The main functionality of TGraphKey is that it performs fast graph isomorphism checking to determine whether two graphs (two keys) are the same (i.e., isomorphic).

Definition at line 7 of file ghash.h.


Constructor & Destructor Documentation

TGraphKey::TGraphKey ( ) [inline]

Definition at line 17 of file ghash.h.

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

Definition at line 5 of file ghash.cpp.

                                            : 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));
  }
}
TGraphKey::TGraphKey ( const TIntV GraphSigV)

Definition at line 12 of file ghash.cpp.

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

Definition at line 19 of file ghash.cpp.

                                           : 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));
  }
}
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) {
}

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

Saves the graph to the .DOT file format and calls GraphViz to draw it.

Output type is determined by the OutFNm file extension (.ps, .png).

Definition at line 180 of file ghash.cpp.

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

Returns the number of edges in the graph.

Definition at line 33 of file ghash.h.

{ return EdgeV.Len(); }

Returns the directed graph stored in the GraphKey object.

Definition at line 47 of file ghash.cpp.

                                   {
  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;
}
int TGraphKey::GetNodes ( ) const [inline]

Returns the number of nodes in the graph.

Definition at line 31 of file ghash.h.

{ return Nodes; }
int TGraphKey::GetPrimHashCd ( ) const [inline]

Definition at line 27 of file ghash.h.

{ return abs(SigV.GetPrimHashCd() ^ VariantId); }
int TGraphKey::GetSecHashCd ( ) const [inline]

Definition at line 28 of file ghash.h.

{ return abs(SigV.GetSecHashCd() ^ VariantId<<8); }
int TGraphKey::GetSigLen ( ) const [inline]

Returns the length of the signature vector of a graph.

Signature is a set of statistics that is used to quickly determine whether the two graphs could be isomorphic. Graphs that differ in their signatures are guaranteed to be non-isomorphic while graphs with identical signatures could still be isomorphic.

Definition at line 40 of file ghash.h.

{ return SigV.Len(); }
int TGraphKey::GetVariant ( ) const [inline]

Returns the graph variant Id.

When the hash table contains multiple non-isomorphic graphs with identical signatures we assign each a unique VariantId.

Definition at line 45 of file ghash.h.

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

Checks whether directed graph Key1 is isomorphic to the directed graph Key2 under node Id permutation NodeIdMap.

The function does not consider all possible permutations (mappings) between node Ids but only considers mapping in NodeIdMap.

Definition at line 186 of file ghash.cpp.

                                                                                               {
  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;
}
bool TGraphKey::IsIsomorph ( const TGraphKey Key1,
const TGraphKey Key2,
const TVec< TIntV > &  NodeIdMapV 
) [static]

Checks whether directed graph Key1 is isomorphic to the directed graph Key2 under all the permutations of node Ids stored in NodeIdMapV.

Definition at line 197 of file ghash.cpp.

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

Checks whether directed graph Key1 is isomorphic to the directed graph Key2 under all the permutations of node Ids stored in NodeIdMapV and returns the Id of the permutation of node Ids (IsoPermId) which makes the two graphs isomorphic.

Definition at line 202 of file ghash.cpp.

                                                                                                                      {
  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;
}
TGraphKey & TGraphKey::operator= ( const TGraphKey GraphKey)

Definition at line 37 of file ghash.cpp.

                                                           {
  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 25 of file ghash.h.

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

Definition at line 32 of file ghash.cpp.

                                      {
  Nodes.Save(SOut);  EdgeV.Save(SOut);
  SigV.Save(SOut);  VariantId.Save(SOut);
}
void TGraphKey::SaveGViz ( const TStr OutFNm,
const TStr Desc = TStr(),
const TStr NodeAttrs = "",
const int &  Size = -1 
) const

Saves the graph to the .DOT file format used by GraphViz.

Use ".dot" as file extension for OutFNm.

Definition at line 154 of file ghash.cpp.

                                                                                                           {
  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);
}
void TGraphKey::SaveTxt ( FILE *  F) const

Saves the graph as a list of edges.

Definition at line 147 of file ghash.cpp.

                                     {
  fprintf(F, "#GraphKey. 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());
  }
}
void TGraphKey::SetEdgeV ( const TIntPrV EdgeIdV) [inline]

Returns a vector of directed edges of a graph.

Definition at line 49 of file ghash.h.

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

Sets the Variant Id of a given graph.

Definition at line 47 of file ghash.h.

{ VariantId = Variant; }
void TGraphKey::TakeGraph ( const PNGraph Graph)

Creates a key from a given directed graph.

Nodes get renumbered to have Ids 0...N-1. Does not create a graph signature.

Definition at line 58 of file ghash.cpp.

                                              {
  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();
}
void TGraphKey::TakeGraph ( const PNGraph Graph,
TIntPrV NodeMap 
)

Creates a key from a given directed graph.

Parameter NodeMap stores the correspondence of old to new node Ids (0...N-1). Does not create a graph signature. Nodes are renumbered.

Definition at line 74 of file ghash.cpp.

                                                                {
  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();
}
void TGraphKey::TakeSig ( const PNGraph Graph,
const int &  MnSvdGraph,
const int &  MxSvdGraph 
)

Creates a signature for a given directed graph.

The function only creates the signature vector but does not copy the graph.

Definition at line 94 of file ghash.cpp.

                                                                                          {
  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);
  // compose the signature: nodes, edges, sorted in- and out- degree sequence
  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();
}

Member Data Documentation

Definition at line 13 of file ghash.h.

Definition at line 12 of file ghash.h.

const int TGraphKey::RoundTo = 4 [static]

Definition at line 9 of file ghash.h.

Definition at line 14 of file ghash.h.

Definition at line 15 of file ghash.h.


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