Small Directed Graphs. More...

#include <ghash.h>

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.

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

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.

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

PNGraph TGraphKey::GetNGraph ( ) const

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