TGHash< TDat > Class Template Reference

Graph Hash Table. More...

#include <ghash.h>

Collaboration diagram for TGHash< TDat >:

Public Types
typedef THash< TGraphKey, TDat > ::TIter	TIter

Public Member Functions
	TGHash (const bool &HashTrees, const int &MaxIsoCheck=8, const int &MaxSvdGraph=500)
	Default contructor. More...
	TGHash (TSIn &SIn)
void	Save (TSOut &SOut) const
const TDat &	operator[] (const int &KeyId) const
	Accesses the data at hash table position index KeyId. More...
TDat &	operator[] (const int &KeyId)
	Accesses the data at hash table position index KeyId. More...
const TDat &	operator() (const TGraphKey &Key) const
	Accesses the data of graph-key Key. More...
TDat &	operator() (const TGraphKey &Key)
	Accesses the data of graph-key Key. More...
TIter	BegI () const
	Returns iterator to the first element of the hash table. More...
TIter	EndI () const
	Returns iterator to one past the last element of the hash table. More...
TIter	GetI (const int &KeyId) const
	Returns iterator to a key at position index KeyId. More...
bool	HashTrees () const
	Returns whether the hash table only hashes trees and not arbitrary directed graphs. More...
void	Gen (const int &ExpectVals)
	Initializes the hash table for the expected number of keys ExpectVals. More...
void	Clr (const bool &DoDel=true, const int &NoDelLim=-1)
	Removes all the elements from the hash table. More...
bool	Empty () const
	Tests whether the hash table is empty. More...
int	Len () const
	Returns the number of keys in the hash table. More...
int	GetPorts () const
	Returns the number of ports in the hash table. More...
bool	IsAutoSize () const
	Tests whether the hash table automatically adjusts the number of ports based on the number of keys. More...
int	GetMxKeyIds () const
	Returns the maximum key Id of any element in the hash table. More...
bool	IsKeyIdEqKeyN () const
	Tests whether there are any unused slots in the hash table. More...
int	AddKey (const PNGraph &Graph)
	Adds a key Graph to the table and returns its KeyId. More...
TDat &	AddDat (const PNGraph &Graph)
	Adds a key Graph to the table and returns its data value. More...
TDat &	AddDat (const PNGraph &Graph, const TDat &Dat)
	Adds a key Graph to the table, sets its data value to value of Dat and returns Dat. More...
bool	IsKey (const PNGraph &Graph) const
	Test whether Graph is an existing key in the hash table. More...
int	GetKeyId (const PNGraph &Graph) const
	Returns the KeyId (position index) of key Graph. More...
const TDat &	GetDat (const PNGraph &Graph) const
	Returns the data associated with key Graph. More...
TDat &	GetDat (const PNGraph &Graph)
	Returns the data associated with key Graph. More...
const TGraphKey &	GetKey (const int &KeyId) const
	Returns the GraphKey with position index KeyId. More...
int	GetKeyId (const TGraphKey &Key) const
	Returns the KeyId for a given Key. More...
bool	IsKey (const TGraphKey &Key) const
	Tests whether a given Key exists in the hash table. More...
bool	IsKey (const TGraphKey &Key, int &KeyId) const
	Tests whether a given Key exists in the hash table. More...
bool	IsKeyId (const int &KeyId) const
	Tests whether there exists a key at given position index KeyId. More...
const TDat &	GetDat (const TGraphKey &Key) const
	Returns data with a given graph Key. More...
TDat &	GetDat (const TGraphKey &Key)
	Returns data with a given graph Key. More...
const TDat &	GetDatId (const int &KeyId) const
	Returns data at a given position index KeyId. More...
TDat &	GetDatId (const int &KeyId)
	Returns data at a given position index KeyId. More...
void	GetKeyDat (const int &KeyId, TGraphKey &Key, TDat &Dat) const
	Returns Key and Data at a given position index KeyId. More...
bool	IsKeyGetDat (const TGraphKey &Key, TDat &Dat) const
	Test whether Key exists and sets its data to Dat. More...
bool	GetNodeMap (const PNGraph &Graph, TIntPrV &NodeMapV) const
	Returns the mapping of node Ids of the Graph to those of the graph-key in the hash table. More...
bool	GetNodeMap (const PNGraph &Graph, TIntPrV &NodeMapV, int &KeyId) const
	Returns the mapping of node Ids of the Graph to those of the graph-key in the hash table and the Graph KeyId. More...
int	FFirstKeyId () const
	Finds first KeyId. More...
bool	FNextKeyId (int &KeyId) const
	Finds next KeyId. More...
void	GetKeyV (TVec< TGraphKey > &KeyV) const
	Returns a vector of keys stored in the hash table. More...
void	GetDatV (TVec< TDat > &DatV) const
	Returns a vector of data elements stored in the hash table. More...
void	GetKeyIdByDat (TIntV &KeyIdV, const bool &Asc=true) const
	Returns a vector of KeyIds of hash table elements sorted by their data value. More...
void	GetKeyIdByGSz (TIntV &KeyIdV, const bool &Asc=true) const
	Returns a vector of KeyIds of hash table elements sorted by their graph size. More...
void	GetKeyDatPrV (TVec< TPair< TGraphKey, TDat > > &KeyDatPrV) const
	Returns a vector of pairs (Key, Data) elements stored in the hash table. More...
void	GetDatKeyPrV (TVec< TPair< TDat, TGraphKey > > &DatKeyPrV) const
	Returns a vector of pairs (Data, Key) elements stored in the hash table. More...
void	Defrag ()
	Removes unused slots from the hash table. More...
void	Pack ()
	Frees the unused memory by the hash table. More...
void	DrawGViz (const int &KeyId, const TStr &OutFNmPref, const TStr &OutputType="gif", TStr Desc="") const
	Saves a given graph with key Id KeyId in DOT format and calls the GraphViz to draw it. More...
void	DrawGViz (const TIntV &KeyIdV, const TStr &OutFNmPref, const TStr &OutputType="gif") const
	Saves a set of graphs with key Ids KeyIdV in DOT format and calls the GraphViz to draw them. More...
void	SaveTxt (const TStr &OutFNm, const TStr &Desc, const TStr &DatColNm, const bool &SortByKeyVal=true) const
	Saves all graphs stored in the hash table into a text file. More...
void	SaveDetailTxt (const TStr &OutFNm, const TStr &Desc, const TStr &DatColNm) const
	Saves all graphs stored in the hash table into a text file and include additional information. More...

Private Member Functions
void	InitPermutations ()
int	IsGetKeyId (const PNGraph &Graph) const
int	IsGetKeyId (const PNGraph &Graph, TGraphKey &GKey) const
int	IsGetKeyId (const PNGraph &Graph, TGraphKey &GKey, TIntPrV &NodeMap) const

Private Attributes
TInt	MxIsoCheck
TInt	MxSvdGraph
THash< TInt, TVec< TIntV > >	GSzToPermH
TBool	HashOnlyTrees
THash< TGraphKey, TDat >	GraphH

Detailed Description

template<class TDat>
class TGHash< TDat >

Graph Hash Table.

Keys in this hash table are (little) directed graphs. The class is useful for counting frequencies of small subgraphs or information cascades. For small graphs with less than MxIsoCheck nodes the class performs exact isomorphism checking. For graphs with less than MxSvdGraph nodes the class performs approximate isomorphism checking by comparing a numeric SVD-based signatures of two graphs. For graphs with more than MxSvdGraph nodes the class performs approximate isorphism checking by comparing only the signature based on simple graph statistics. For hashing trees (tree is encoded as a directed graph where children point to the parent) the class always performs exact isomorphism testing.

Definition at line 103 of file ghash.h.

Member Typedef Documentation

template<class TDat>

typedef THash<TGraphKey, TDat>::TIter TGHash< TDat >::TIter

Definition at line 105 of file ghash.h.

Constructor & Destructor Documentation

template<class TDat >

TGHash< TDat >::TGHash	(	const bool &	HashTrees,
		const int &	MaxIsoCheck = 8,
		const int &	MaxSvdGraph = 500
	)

Default contructor.

For hashing trees and not general graphs, set HashTrees=true. A tree is a directed graph where children point to the parent. In this case exact isomorphism checking will be performed. For hashing general graphs, set HashTrees=false. MaxIsoCheck is the maximum number of nodes for which we perform brute force exact isomorphism check. For larger graph the isomorphism test is only approximate.

Definition at line 304 of file ghash.h.

References TGHash< TDat >::InitPermutations().

                                                                                          :
 MxIsoCheck(MaxIsoCheck), MxSvdGraph(MaxSvdGraph), GSzToPermH(), HashOnlyTrees(HashTrees), GraphH() {
  if (! HashTrees) {
    InitPermutations();
  }
}

Here is the call graph for this function:

template<class TDat >

TGHash< TDat >::TGHash

(

TSIn &

SIn

)

Definition at line 312 of file ghash.h.

References TGHash< TDat >::HashOnlyTrees, and TGHash< TDat >::InitPermutations().

                              : MxIsoCheck(SIn), MxSvdGraph(SIn), GSzToPermH(), HashOnlyTrees(SIn), GraphH(SIn) {
  if (! HashOnlyTrees) {
    InitPermutations();
  }
}

Here is the call graph for this function:

Member Function Documentation

template<class TDat>

TDat& TGHash< TDat >::AddDat ( const PNGraph &  Graph )

inline

Adds a key Graph to the table and returns its data value.

If the key already exists the function returns the data associated with that existing key.

Definition at line 177 of file ghash.h.

Referenced by TDGHashGraphCounter::operator()().

{ return GraphH[AddKey(Graph)]; }

Here is the caller graph for this function:

template<class TDat>

TDat& TGHash< TDat >::AddDat ( const PNGraph &  Graph, const TDat &  Dat  )

inline

Adds a key Graph to the table, sets its data value to value of Dat and returns Dat.

If the key already exists the function sets the data value of that existing key.

Definition at line 181 of file ghash.h.

{ return GraphH[AddKey(Graph)] = Dat; }

template<class TDat >

int TGHash< TDat >::AddKey

(

const PNGraph &

Graph

)

Adds a key Graph to the table and returns its KeyId.

KeyId is position index in the hash table. If the key already exists the function returns KeyId of that existing key.

Definition at line 327 of file ghash.h.

References Fail, TGraphKey::GetNodes(), TSnap::GetTreeSig(), IAssert, TGraphKey::IsIsomorph(), TSnap::IsTree(), TGraphKey::SetVariant(), TGraphKey::TakeGraph(), and TGraphKey::TakeSig().

Referenced by TGHash< TUInt64 >::AddDat().

                                             {
  if (HashOnlyTrees) {
    int RootNId;  IAssert(TSnap::IsTree(Graph, RootNId));
    TIntV TreeSig;  TSnap::GetTreeSig(Graph, RootNId, TreeSig);
    TGraphKey GKey(TreeSig);
    const int KeyId = GraphH.GetKeyId(GKey);
    if (KeyId == -1) {
      GKey.TakeGraph(Graph);
      return GraphH.AddKey(GKey);
    }
    return KeyId;
  } else {
    TGraphKey GKey;
    GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph); // get signature
    const int Nodes = GKey.GetNodes();
    if (Nodes > 2 && Nodes <= MxIsoCheck) {
      GKey.TakeGraph(Graph);
      // Check all variants with same signature
      for (int variant = 1; ; variant++) {
        GKey.SetVariant(variant);
        int KeyId = GraphH.GetKeyId(GKey);
        if (KeyId == -1) { // Key of such signature and variant does not exist yet.
          KeyId = GraphH.AddKey(GKey);
          return KeyId;
        }
        if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes))) { // Graph isomorphism test
          return KeyId;  // Found isomorphic graph.
        }
      }
    } else {
      const int KeyId = GraphH.GetKeyId(GKey);
      if (KeyId == -1) {
        GKey.TakeGraph(Graph);
        return GraphH.AddKey(GKey);
      }
      return KeyId;
    }
  }
  Fail;
  return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TDat>

TIter TGHash< TDat >::BegI ( ) const

inline

Returns iterator to the first element of the hash table.

Definition at line 139 of file ghash.h.

{ return GraphH.BegI(); }

template<class TDat>

void TGHash< TDat >::Clr ( const bool &  DoDel = true, const int &  NoDelLim = -1  )

inline

Removes all the elements from the hash table.

If DoDel=true the data structure will free the memory, otherwise the object stays initialized (which makes subsequent insertion of keys much faster).

Definition at line 154 of file ghash.h.

{ GraphH.Clr(DoDel, NoDelLim); }

template<class TDat>

void TGHash< TDat >::Defrag ( )

inline

Removes unused slots from the hash table.

Slots get freed after removing keys from the table.

Definition at line 272 of file ghash.h.

{ GraphH.Defrag(); }

template<class TDat >

void TGHash< TDat >::DrawGViz	(	const int &	KeyId,
		const TStr &	OutFNmPref,
		const TStr &	OutputType = "gif",
		TStr	Desc = ""
	)		const

Saves a given graph with key Id KeyId in DOT format and calls the GraphViz to draw it.

Definition at line 480 of file ghash.h.

References TStr::CStr(), TStr::Fmt(), TGraphKey::GetEdges(), TGraphKey::GetNodes(), TSnap::TSnapDetail::GVizDoLayout(), gvlDot, IAssert, and TGraphKey::SaveGViz().

                                                                                                             {
  IAssert(OutputType == "ps" || OutputType == "gif" || OutputType == "png");
  const TGraphKey& GKey = GetKey(KeyId);
  const TStr Desc1 = TStr::Fmt("%s (%d, %d)", Desc.CStr(), GKey.GetNodes(), GKey.GetEdges());
  GKey.SaveGViz(OutFNmPref+".dot", Desc1);
  TSnap::TSnapDetail::GVizDoLayout(OutFNmPref+".dot", OutFNmPref+"."+OutputType, gvlDot);
}

Here is the call graph for this function:

template<class TDat >

void TGHash< TDat >::DrawGViz	(	const TIntV &	KeyIdV,
		const TStr &	OutFNmPref,
		const TStr &	OutputType = "gif"
	)		const

Saves a set of graphs with key Ids KeyIdV in DOT format and calls the GraphViz to draw them.

Definition at line 489 of file ghash.h.

References TStr::CStr(), TStr::Fmt(), TGraphKey::GetEdges(), TGraphKey::GetNodes(), TExeTm::GetTmStr(), TSnap::TSnapDetail::GVizDoLayout(), gvlDot, IAssert, TVec< TVal, TSizeTy >::Len(), and TGraphKey::SaveGViz().

                                                                                                     {
  IAssert(OutputType == "ps" || OutputType == "gif" || OutputType == "png");
  TExeTm ExeTm;
  printf("Plotting %d graphs\n", KeyIdV.Len());
  for (int i = 0; i < KeyIdV.Len(); i++) {
    const TStr FNm = TStr::Fmt("%s.%03d.key%d.", OutFNmPref.CStr(), i+1, KeyIdV[i]());
    const TStr Desc = TStr::Fmt("KeyId:%d", KeyIdV[i]());
    const TGraphKey& GKey = GetKey(KeyIdV[i]);
    printf("\r  %d  g(%d, %d)    ", i, GKey.GetNodes(), GKey.GetEdges());
    GKey.SaveGViz(FNm+"dot", Desc);
    TSnap::TSnapDetail::GVizDoLayout(FNm+"dot", FNm+OutputType, gvlDot);
  }
  printf("done [%s].\n", ExeTm.GetTmStr());
}

Here is the call graph for this function:

template<class TDat>

bool TGHash< TDat >::Empty ( ) const

inline

Tests whether the hash table is empty.

Definition at line 156 of file ghash.h.

{ return GraphH.Empty(); }

template<class TDat>

TIter TGHash< TDat >::EndI ( ) const

inline

Returns iterator to one past the last element of the hash table.

Definition at line 141 of file ghash.h.

{ return GraphH.EndI(); }

template<class TDat>

int TGHash< TDat >::FFirstKeyId ( ) const

inline

Finds first KeyId.

Used for traversing the elements of the hash table: for (int KeyId = GHash.FFirstKeyId(); GHash.FNextKeyId(KeyId); ) { }

Definition at line 245 of file ghash.h.

{ return 0-1; }

template<class TDat>

bool TGHash< TDat >::FNextKeyId ( int &  KeyId ) const

inline

Finds next KeyId.

Used for traversing the elements of the hash table: for (int KeyId = GHash.FFirstKeyId(); GHash.FNextKeyId(KeyId); ) { }

Definition at line 250 of file ghash.h.

{ return GraphH.FNextKeyId(KeyId); }

template<class TDat>

void TGHash< TDat >::Gen ( const int &  ExpectVals )

inline

Initializes the hash table for the expected number of keys ExpectVals.

Definition at line 149 of file ghash.h.

{ GraphH.Gen(ExpectVals); }

template<class TDat>

const TDat& TGHash< TDat >::GetDat ( const PNGraph &  Graph ) const

inline

Returns the data associated with key Graph.

If the key does not exist the function aborts.

Definition at line 192 of file ghash.h.

Referenced by TDGHashGraphCounter::operator()().

{ return GraphH[GetKeyId(Graph)]; }

Here is the caller graph for this function:

template<class TDat>

TDat& TGHash< TDat >::GetDat ( const PNGraph &  Graph )

inline

Returns the data associated with key Graph.

If the key does not exist the function aborts.

Definition at line 196 of file ghash.h.

{ return GraphH[GetKeyId(Graph)]; }

template<class TDat>

const TDat& TGHash< TDat >::GetDat ( const TGraphKey &  Key ) const

inline

Returns data with a given graph Key.

If the key does not exist the function aborts.

Definition at line 213 of file ghash.h.

{ return GraphH.GetDat(Key); }

template<class TDat>

TDat& TGHash< TDat >::GetDat ( const TGraphKey &  Key )

inline

Returns data with a given graph Key.

If the key does not exist the function aborts.

Definition at line 217 of file ghash.h.

{ return GraphH.GetDat(Key); }

template<class TDat>

const TDat& TGHash< TDat >::GetDatId ( const int &  KeyId ) const

inline

Returns data at a given position index KeyId.

If KeyId is out of bounds the function fails.

Definition at line 221 of file ghash.h.

{ return GraphH[KeyId]; }

template<class TDat>

TDat& TGHash< TDat >::GetDatId ( const int &  KeyId )

inline

Returns data at a given position index KeyId.

If KeyId is out of bounds the function fails.

Definition at line 225 of file ghash.h.

{ return GraphH[KeyId]; }

template<class TDat>

void TGHash< TDat >::GetDatKeyPrV ( TVec< TPair< TDat, TGraphKey > > &  DatKeyPrV ) const

inline

Returns a vector of pairs (Data, Key) elements stored in the hash table.

Definition at line 267 of file ghash.h.

{ GraphH.GetDatKeyPrV(DatKeyPrV); }

template<class TDat>

void TGHash< TDat >::GetDatV ( TVec< TDat > &  DatV ) const

inline

Returns a vector of data elements stored in the hash table.

Definition at line 254 of file ghash.h.

{ GraphH.GetDatV(DatV); }

template<class TDat>

TIter TGHash< TDat >::GetI ( const int &  KeyId ) const

inline

Returns iterator to a key at position index KeyId.

Definition at line 143 of file ghash.h.

{ return GraphH.GetI(KeyId); }

template<class TDat>

const TGraphKey& TGHash< TDat >::GetKey ( const int &  KeyId ) const

inline

Returns the GraphKey with position index KeyId.

Definition at line 199 of file ghash.h.

{ return GraphH.GetKey(KeyId); }

template<class TDat>

void TGHash< TDat >::GetKeyDat ( const int &  KeyId, TGraphKey &  Key, TDat &  Dat  ) const

inline

Returns Key and Data at a given position index KeyId.

Definition at line 228 of file ghash.h.

{ GraphH.GetKeyDat(KeyId, Key, Dat); }

template<class TDat>

void TGHash< TDat >::GetKeyDatPrV ( TVec< TPair< TGraphKey, TDat > > &  KeyDatPrV ) const

inline

Returns a vector of pairs (Key, Data) elements stored in the hash table.

Definition at line 265 of file ghash.h.

{ GraphH.GetKeyDatPrV(KeyDatPrV); }

template<class TDat>

int TGHash< TDat >::GetKeyId ( const PNGraph &  Graph ) const

inline

Returns the KeyId (position index) of key Graph.

If the key does not exist, the function returns -1.

Definition at line 188 of file ghash.h.

Referenced by TGHash< TUInt64 >::GetDat().

{ return IsGetKeyId(Graph); }

Here is the caller graph for this function:

template<class TDat>

int TGHash< TDat >::GetKeyId ( const TGraphKey &  Key ) const

inline

Returns the KeyId for a given Key.

If the key does not exist, the function returns -1.

Definition at line 203 of file ghash.h.

{ return GraphH.GetKeyId(Key); }

template<class TDat >

void TGHash< TDat >::GetKeyIdByDat	(	TIntV &	KeyIdV,
		const bool &	Asc = true
	)		const

Returns a vector of KeyIds of hash table elements sorted by their data value.

Asc=true: sort in ascending order, otherwise in descending order.

Definition at line 454 of file ghash.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), and TVec< TVal, TSizeTy >::Sort().

                                                                     {
  TVec<TQuad<TDat, TInt,TInt, TInt> > DatKeyIdV(Len(), 0); // <TDat,Nodes,Edges,KeyId>
  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
    DatKeyIdV.Add(TQuad<TDat, TInt,TInt, TInt>(GetDatId(i), GetKey(i).GetNodes(), GetKey(i).GetEdges(), i));
  }
  DatKeyIdV.Sort(Asc);
  KeyIdV.Gen(Len(), 0);
  for (int i = 0; i < Len(); i++) {
    KeyIdV.Add(DatKeyIdV[i].Val4);
  }
}

Here is the call graph for this function:

template<class TDat >

void TGHash< TDat >::GetKeyIdByGSz	(	TIntV &	KeyIdV,
		const bool &	Asc = true
	)		const

Returns a vector of KeyIds of hash table elements sorted by their graph size.

Asc=true: sort in ascending order, otherwise in descending order. Graph size is the number of nodes and edges.

Definition at line 467 of file ghash.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), and TVec< TVal, TSizeTy >::Sort().

                                                                     {
  TVec<TQuad<TInt,TInt, TDat, TInt> > DatKeyIdV(Len(), 0); // <Nodes,Edges,TDat,KeyId>
  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
    DatKeyIdV.Add(TQuad< TInt,TInt, TDat, TInt>(GetKey(i).GetNodes(), GetKey(i).GetEdges(), GetDatId(i), i));
  }
  DatKeyIdV.Sort(Asc);
  KeyIdV.Gen(Len(), 0);
  for (int i = 0; i < Len(); i++) {
    KeyIdV.Add(DatKeyIdV[i].Val4);
  }
}

Here is the call graph for this function:

template<class TDat>

void TGHash< TDat >::GetKeyV ( TVec< TGraphKey > &  KeyV ) const

inline

Returns a vector of keys stored in the hash table.

Definition at line 252 of file ghash.h.

{ GraphH.GetKeyV(KeyV); }

template<class TDat>

int TGHash< TDat >::GetMxKeyIds ( ) const

inline

Returns the maximum key Id of any element in the hash table.

Definition at line 164 of file ghash.h.

{ return GraphH.GetMxKeyIds(); }

template<class TDat >

bool TGHash< TDat >::GetNodeMap	(	const PNGraph &	Graph,
		TIntPrV &	NodeMapV
	)		const

Returns the mapping of node Ids of the Graph to those of the graph-key in the hash table.

The function assumes the Graph exists as a key in the table. Otherwise it returns false.

Definition at line 407 of file ghash.h.

                                                                           {
  int KeyId;
  return GetNodeMap(Graph, NodeMapV, KeyId);
}

template<class TDat >

bool TGHash< TDat >::GetNodeMap	(	const PNGraph &	Graph,
		TIntPrV &	NodeMapV,
		int &	KeyId
	)		const

Returns the mapping of node Ids of the Graph to those of the graph-key in the hash table and the Graph KeyId.

The function assumes the Graph exists as a key in the table. Otherwise it returns false.

Definition at line 413 of file ghash.h.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegNI(), TVec< TVal, TSizeTy >::Clr(), Fail, TVec< TVal, TSizeTy >::GetDat(), TNGraph::TNodeI::GetId(), TNGraph::GetNodes(), TSnap::GetTreeSig(), IAssert, TGraphKey::IsIsomorph(), TSnap::IsTree(), TVec< TVal, TSizeTy >::Len(), TGraphKey::SetVariant(), TGraphKey::TakeGraph(), and TGraphKey::TakeSig().

                                                                                       {
  NodeMapV.Clr(false);
  if (HashOnlyTrees) {
    int RootNId;  IAssert(TSnap::IsTree(Graph, RootNId));
    TIntV TreeSig;  TSnap::GetTreeSig(Graph, RootNId, TreeSig, NodeMapV);
    TGraphKey GKey(TreeSig);
    KeyId = GraphH.GetKeyId(GKey);
    return KeyId != -1;
  } else {
    const int Nodes = Graph->GetNodes();
    int IsoPermId = -1;
    NodeMapV.Clr(false);
    if (Nodes == 0) { return true; }
    else if (Nodes == 1) {
      NodeMapV.Add(TIntPr(Graph->BegNI().GetId(), 0));  return true; }
    else if (Nodes <= MxIsoCheck) {
      TGraphKey GKey;
      GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph);
      GKey.TakeGraph(Graph, NodeMapV);
      for (int variant = 1; ; variant++) {
        GKey.SetVariant(variant);
        KeyId = GraphH.GetKeyId(GKey);
        if (KeyId == -1) { return false; }
        if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes), IsoPermId)) {
          const TIntV& K1K2Perm = GSzToPermH.GetDat(Nodes)[IsoPermId];
          // map from graph to key1 to key2
          for  (int i = 0; i < NodeMapV.Len(); i++) {
            NodeMapV[i].Val2 = K1K2Perm[NodeMapV[i].Val2]; }
          return true;
        }
      }
      return false;
    } else {
      return false; // graph too big to find the mapping
    }
  }
  Fail;
  return false;
}

Here is the call graph for this function:

template<class TDat>

int TGHash< TDat >::GetPorts ( ) const

inline

Returns the number of ports in the hash table.

Definition at line 160 of file ghash.h.

{ return GraphH.GetPorts(); }

template<class TDat>

bool TGHash< TDat >::HashTrees ( ) const

inline

Returns whether the hash table only hashes trees and not arbitrary directed graphs.

Definition at line 146 of file ghash.h.

{ return HashOnlyTrees; }

template<class TDat >

void TGHash< TDat >::InitPermutations ( )

private

Definition at line 287 of file ghash.h.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::NextPerm(), and TVec< TVal, TSizeTy >::Pack().

Referenced by TGHash< TDat >::TGHash().

                                    {
  GSzToPermH.Clr();
  for (int nodes = 2; nodes <= MxIsoCheck; nodes++) {
    TVec<TIntV> NodePermutationV;
    TIntV NodeIdV(nodes, 0);
    for (int i = 0; i < nodes; i++)  NodeIdV.Add(i);
    NodeIdV.Pack();
    NodePermutationV.Add(NodeIdV);
    while (NodeIdV.NextPerm()) {
      NodePermutationV.Add(NodeIdV);
    }
    NodePermutationV.Pack();
    GSzToPermH.AddDat(nodes, NodePermutationV);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TDat>

bool TGHash< TDat >::IsAutoSize ( ) const

inline

Tests whether the hash table automatically adjusts the number of ports based on the number of keys.

Definition at line 162 of file ghash.h.

{ return GraphH.IsAutoSize(); }

template<class TDat >

int TGHash< TDat >::IsGetKeyId ( const PNGraph &  Graph ) const

private

Definition at line 370 of file ghash.h.

Referenced by TGHash< TUInt64 >::GetKeyId(), and TGHash< TUInt64 >::IsKey().

                                                       {
  TGraphKey GKey;
  return IsGetKeyId(Graph, GKey);
}

Here is the caller graph for this function:

template<class TDat >

int TGHash< TDat >::IsGetKeyId ( const PNGraph &  Graph, TGraphKey &  GKey  ) const

private

Definition at line 376 of file ghash.h.

References Fail, TGraphKey::GetNodes(), TSnap::GetTreeSig(), IAssert, TGraphKey::IsIsomorph(), TSnap::IsTree(), TGraphKey::SetVariant(), TGraphKey::TakeGraph(), and TGraphKey::TakeSig().

                                                                        {
  if (HashOnlyTrees) {
    // For trees we perform exact isomorshism test based on graph signatures
    int RootNId;  IAssert(TSnap::IsTree(Graph, RootNId));
    TIntV TreeSig;  TSnap::GetTreeSig(Graph, RootNId, TreeSig);
    GKey = TGraphKey(TreeSig);
    const int KeyId = GraphH.GetKeyId(GKey);
    return KeyId;
  } else {
    // For small graphs  of less than MxIsoCheck nodes we perform brute force isomorphism checking
    GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph);
    const int Nodes = GKey.GetNodes();
    if (Nodes > 2 && Nodes <= MxIsoCheck) {
      GKey.TakeGraph(Graph);
      for (int variant = 1; ; variant++) {
        GKey.SetVariant(variant);
        int KeyId = GraphH.GetKeyId(GKey); // Is there a graph of the same signature and same VariantId
        if (KeyId == -1) { return -1; }
        if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes))) { return KeyId; } // perform brute force isomorphism check
      }
    } else {
      // For all other graphs we perform approximate graph isomorphism checking
      const int KeyId = GraphH.GetKeyId(GKey);
      return KeyId;
    }
  }
  Fail;
  return -1;
}

Here is the call graph for this function:

template<class TDat>

int TGHash< TDat >::IsGetKeyId ( const PNGraph &  Graph, TGraphKey &  GKey, TIntPrV &  NodeMap  ) const

private

template<class TDat>

bool TGHash< TDat >::IsKey ( const PNGraph &  Graph ) const

inline

Test whether Graph is an existing key in the hash table.

Definition at line 184 of file ghash.h.

Referenced by TDGHashGraphCounter::operator()().

{ int k=IsGetKeyId(Graph); return k!=-1; }

Here is the caller graph for this function:

template<class TDat>

bool TGHash< TDat >::IsKey ( const TGraphKey &  Key ) const

inline

Tests whether a given Key exists in the hash table.

Definition at line 205 of file ghash.h.

{ return GraphH.IsKey(Key); }

template<class TDat>

bool TGHash< TDat >::IsKey ( const TGraphKey &  Key, int &  KeyId  ) const

inline

Tests whether a given Key exists in the hash table.

Definition at line 207 of file ghash.h.

{ return GraphH.IsKey(Key, KeyId); }

template<class TDat>

bool TGHash< TDat >::IsKeyGetDat ( const TGraphKey &  Key, TDat &  Dat  ) const

inline

Test whether Key exists and sets its data to Dat.

Definition at line 230 of file ghash.h.

{ return GraphH.IsKeyGetDat(Key, Dat); }

template<class TDat>

bool TGHash< TDat >::IsKeyId ( const int &  KeyId ) const

inline

Tests whether there exists a key at given position index KeyId.

Definition at line 209 of file ghash.h.

{ return GraphH.IsKeyId(KeyId); }

template<class TDat>

bool TGHash< TDat >::IsKeyIdEqKeyN ( ) const

inline

Tests whether there are any unused slots in the hash table.

Slots get freed after removing keys from the table.

Definition at line 168 of file ghash.h.

{ return GraphH.IsKeyIdEqKeyN(); }

template<class TDat>

int TGHash< TDat >::Len ( ) const

inline

Returns the number of keys in the hash table.

Definition at line 158 of file ghash.h.

{  return GraphH.Len(); }

template<class TDat>

const TDat& TGHash< TDat >::operator() ( const TGraphKey &  Key ) const

inline

Accesses the data of graph-key Key.

Definition at line 135 of file ghash.h.

{ return GraphH.GetDat(Key); }

template<class TDat>

TDat& TGHash< TDat >::operator() ( const TGraphKey &  Key )

inline

Accesses the data of graph-key Key.

Definition at line 137 of file ghash.h.

{ return GraphH.GetDat(Key); }

template<class TDat>

const TDat& TGHash< TDat >::operator[] ( const int &  KeyId ) const

inline

Accesses the data at hash table position index KeyId.

Definition at line 131 of file ghash.h.

{ return GraphH[KeyId]; }

template<class TDat>

TDat& TGHash< TDat >::operator[] ( const int &  KeyId )

inline

Accesses the data at hash table position index KeyId.

Definition at line 133 of file ghash.h.

{ return GraphH[KeyId]; }

template<class TDat>

void TGHash< TDat >::Pack ( )

inline

Frees the unused memory by the hash table.

Definition at line 274 of file ghash.h.

{ GraphH.Pack(); }

template<class TDat >

void TGHash< TDat >::Save

(

TSOut &

SOut

)

const

Definition at line 319 of file ghash.h.

                                         {
  MxIsoCheck.Save(SOut);
  MxSvdGraph.Save(SOut);
  HashOnlyTrees.Save(SOut);
  GraphH.Save(SOut);
}

template<class TDat >

void TGHash< TDat >::SaveDetailTxt	(	const TStr &	OutFNm,
		const TStr &	Desc,
		const TStr &	DatColNm
	)		const

Saves all graphs stored in the hash table into a text file and include additional information.

Definition at line 523 of file ghash.h.

References TStr::CStr(), and TVec< TVal, TSizeTy >::Len().

                                                                                                 {
  TIntV KeyIdV;  GetKeyIdByDat(KeyIdV, false);
  FILE *F = fopen(OutFNm.CStr(), "wt");
  fprintf(F, "Graph-Hash-Table\n");
  fprintf(F, "%s\n", Desc.CStr());
  fprintf(F, "%d graphs", KeyIdV.Len());
  for (int i = 0; i < KeyIdV.Len(); i++) {
    fprintf(F, "\n\n[%5d]\tRank: %d\n", KeyIdV[i](), i+1);
    fprintf(F, "Dat:  %s\n", GetDat(KeyIdV[i]).GetStr().CStr());
    GetDatId(KeyIdV[i]).SaveTxt(F);
  }
  fclose(F);
}

Here is the call graph for this function:

template<class TDat >

void TGHash< TDat >::SaveTxt	(	const TStr &	OutFNm,
		const TStr &	Desc,
		const TStr &	DatColNm,
		const bool &	SortByKeyVal = true
	)		const

Saves all graphs stored in the hash table into a text file.

Definition at line 505 of file ghash.h.

References TStr::CStr(), TGraphKey::GetEdges(), TGraphKey::GetNodes(), and TVec< TVal, TSizeTy >::Len().

                                                                                                                     {
  TIntV KeyIdV;
  if (SortByKeyVal) GetKeyIdByDat(KeyIdV, false);
  else GetKeyIdByGSz(KeyIdV, true);
  FILE *F = fopen(OutFNm.CStr(), "wt");
  fprintf(F, "Graph-Hash-Table");
  fprintf(F, "%s\n", Desc.CStr());
  fprintf(F, "%d graphs\n", KeyIdV.Len());
  fprintf(F, "Rank\tKeyId\tNodes\tEdges\t%s\n", DatColNm.CStr());
  for (int i = 0; i < KeyIdV.Len(); i++) {
    const TGraphKey& Key = GetKey(KeyIdV[i]);
    fprintf(F, "%d\t%d\t%d\t%d\t%s\n", i+1, KeyIdV[i](), Key.GetNodes(), Key.GetEdges(),
      GetDatId(KeyIdV[i]).GetStr().CStr());
  }
  fclose(F);
}

Here is the call graph for this function:

Member Data Documentation

template<class TDat>

THash<TGraphKey, TDat> TGHash< TDat >::GraphH

private

Definition at line 111 of file ghash.h.

Referenced by TGHash< TUInt64 >::AddDat(), TGHash< TUInt64 >::BegI(), TGHash< TUInt64 >::Clr(), TGHash< TUInt64 >::Defrag(), TGHash< TUInt64 >::Empty(), TGHash< TUInt64 >::EndI(), TGHash< TUInt64 >::FNextKeyId(), TGHash< TUInt64 >::Gen(), TGHash< TUInt64 >::GetDat(), TGHash< TUInt64 >::GetDatId(), TGHash< TUInt64 >::GetDatKeyPrV(), TGHash< TUInt64 >::GetDatV(), TGHash< TUInt64 >::GetI(), TGHash< TUInt64 >::GetKey(), TGHash< TUInt64 >::GetKeyDat(), TGHash< TUInt64 >::GetKeyDatPrV(), TGHash< TUInt64 >::GetKeyId(), TGHash< TUInt64 >::GetKeyV(), TGHash< TUInt64 >::GetMxKeyIds(), TGHash< TUInt64 >::GetPorts(), TGHash< TUInt64 >::IsAutoSize(), TGHash< TUInt64 >::IsKey(), TGHash< TUInt64 >::IsKeyGetDat(), TGHash< TUInt64 >::IsKeyId(), TGHash< TUInt64 >::IsKeyIdEqKeyN(), TGHash< TUInt64 >::Len(), TGHash< TUInt64 >::operator()(), TGHash< TUInt64 >::operator[](), and TGHash< TUInt64 >::Pack().

template<class TDat>

THash<TInt, TVec<TIntV> > TGHash< TDat >::GSzToPermH

private

Definition at line 109 of file ghash.h.

template<class TDat>

TBool TGHash< TDat >::HashOnlyTrees

private

Definition at line 110 of file ghash.h.

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

template<class TDat>

TInt TGHash< TDat >::MxIsoCheck

private

Definition at line 107 of file ghash.h.

template<class TDat>

TInt TGHash< TDat >::MxSvdGraph

private

Definition at line 108 of file ghash.h.

---

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

• snap-core/ghash.h