Graph Hash Table. More...

#include <ghash.h>

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.

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

template<class TDat >

TGHash< TDat >::TGHash ( TSIn & SIn )

Definition at line 312 of file ghash.h.

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

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.

177 { return GraphH[AddKey(Graph)]; }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

TGHash::AddKey

int AddKey(const PNGraph &Graph)

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

Definition: ghash.h:327

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.

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

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

TGHash::AddKey

int AddKey(const PNGraph &Graph)

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

Definition: ghash.h:327

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.

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

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.

139 { return GraphH.BegI(); }

THash::BegI

TIter BegI() const

Definition: hash.h:213

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

154 { GraphH.Clr(DoDel, NoDelLim); }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::Clr

void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)

Definition: hash.h:361

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.

272 { GraphH.Defrag(); }

THash::Defrag

void Defrag()

Definition: hash.h:555

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

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

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.

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

template<class TDat>

bool TGHash< TDat >::Empty ( ) const

inline

Tests whether the hash table is empty.

Definition at line 156 of file ghash.h.

156 { return GraphH.Empty(); }

THash::Empty

bool Empty() const

Definition: hash.h:227

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

141 { return GraphH.EndI(); }

THash::EndI

TIter EndI() const

Definition: hash.h:218

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

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

250 { return GraphH.FNextKeyId(KeyId); }

THash::FNextKeyId

bool FNextKeyId(int &KeyId) const

Definition: hash.h:478

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

149 { GraphH.Gen(ExpectVals); }

THash::Gen

void Gen(const int &ExpectVals)

Definition: hash.h:222

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

192 { return GraphH[GetKeyId(Graph)]; }

TGHash::GetKeyId

int GetKeyId(const PNGraph &Graph) const

Returns the KeyId (position index) of key Graph.

Definition: ghash.h:188

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

196 { return GraphH[GetKeyId(Graph)]; }

TGHash::GetKeyId

int GetKeyId(const PNGraph &Graph) const

Returns the KeyId (position index) of key Graph.

Definition: ghash.h:188

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

213 { return GraphH.GetDat(Key); }

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:262

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

217 { return GraphH.GetDat(Key); }

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:262

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

221 { return GraphH[KeyId]; }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

225 { return GraphH[KeyId]; }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

267 { GraphH.GetDatKeyPrV(DatKeyPrV); }

THash::GetDatKeyPrV

void GetDatKeyPrV(TVec< TPair< TDat, TKey > > &DatKeyPrV) const

Definition: hash.h:511

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

254 { GraphH.GetDatV(DatV); }

THash::GetDatV

void GetDatV(TVec< TDat > &DatV) const

Definition: hash.h:492

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

143 { return GraphH.GetI(KeyId); }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::GetI

TIter GetI(const TKey &Key) const

Definition: hash.h:220

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.

199 { return GraphH.GetKey(KeyId); }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::GetKey

const TKey & GetKey(const int &KeyId) const

Definition: hash.h:252

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.

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

THash::GetKeyDat

void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const

Definition: hash.h:271

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

265 { GraphH.GetKeyDatPrV(KeyDatPrV); }

THash::GetKeyDatPrV

void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const

Definition: hash.h:500

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

188 { return IsGetKeyId(Graph); }

TGHash::IsGetKeyId

int IsGetKeyId(const PNGraph &Graph) const

Definition: ghash.h:370

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.

203 { return GraphH.GetKeyId(Key); }

THash::GetKeyId

int GetKeyId(const TKey &Key) const

Definition: hash.h:466

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

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

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.

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

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.

252 { GraphH.GetKeyV(KeyV); }

THash::GetKeyV

void GetKeyV(TVec< TKey > &KeyV) const

Definition: hash.h:484

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

164 { return GraphH.GetMxKeyIds(); }

THash::GetMxKeyIds

int GetMxKeyIds() const

Definition: hash.h:231

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

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

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.

160 { return GraphH.GetPorts(); }

THash::GetPorts

int GetPorts() const

Definition: hash.h:229

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

146 { return HashOnlyTrees; }

TGHash::HashOnlyTrees

TBool HashOnlyTrees

Definition: ghash.h:110

template<class TDat >

void TGHash< TDat >::InitPermutations ( )

private

Definition at line 287 of file ghash.h.

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

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.

162 { return GraphH.IsAutoSize(); }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::IsAutoSize

bool IsAutoSize() const

Definition: hash.h:230

template<class TDat >

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

private

Definition at line 370 of file ghash.h.

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

template<class TDat >

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

private

Definition at line 376 of file ghash.h.

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

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.

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

TGHash::IsGetKeyId

int IsGetKeyId(const PNGraph &Graph) const

Definition: ghash.h:370

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.

205 { return GraphH.IsKey(Key); }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::IsKey

bool IsKey(const TKey &Key) const

Definition: hash.h:258

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.

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

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::IsKey

bool IsKey(const TKey &Key) const

Definition: hash.h:258

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.

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

THash::IsKeyGetDat

bool IsKeyGetDat(const TKey &Key, TDat &Dat) const

Definition: hash.h:274

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

209 { return GraphH.IsKeyId(KeyId); }

THash::IsKeyId

bool IsKeyId(const int &KeyId) const

Definition: hash.h:260

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

168 { return GraphH.IsKeyIdEqKeyN(); }

THash::IsKeyIdEqKeyN

bool IsKeyIdEqKeyN() const

Definition: hash.h:233

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

158 { return GraphH.Len(); }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::Len

int Len() const

Definition: hash.h:228

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.

135 { return GraphH.GetDat(Key); }

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:262

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

137 { return GraphH.GetDat(Key); }

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:262

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

131 { return GraphH[KeyId]; }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

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.

133 { return GraphH[KeyId]; }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

template<class TDat>

void TGHash< TDat >::Pack ( )

inline

Frees the unused memory by the hash table.

Definition at line 274 of file ghash.h.

274 { GraphH.Pack(); }

TGHash::GraphH

THash< TGraphKey, TDat > GraphH

Definition: ghash.h:111

THash::Pack

void Pack()

Definition: hash.h:289

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.

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

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.

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

Member Data Documentation

template<class TDat>

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

private

Definition at line 111 of file ghash.h.

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.

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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class TDat> class TGHash< TDat >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class TDat>
class TGHash< TDat >