#include <ghash.h>

Collaboration diagram for TGraphKey:

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
	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.

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

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.

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]

Returns the number of edges in the graph.

Definition at line 33 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

Returns the directed graph stored in the GraphKey object.

Definition at line 47 of file ghash.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::Defrag(), EdgeV, GetEdges(), GetNodes(), and TNGraph::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]

Returns the number of nodes in the graph.

Definition at line 31 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 27 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 28 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]

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.

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

{ return SigV.Len(); }

Here is the call graph for this function:

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.

References VariantId.

{ 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.

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]`

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.

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]`

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.

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 25 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

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.

References TStr::CStr(), EdgeV, TVec< TVal >::Empty(), TStr::Empty(), 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

Saves the graph as a list of edges.

Definition at line 147 of file ghash.cpp.

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

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

Here is the call graph for this function:

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

Returns a vector of directed edges of a graph.

Definition at line 49 of file ghash.h.

References EdgeV.

{ 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.

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 )

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.

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
	)

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.

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
	)

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.

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(), TSvd::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);
  // 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();
}