SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Private Member Functions | Private Attributes
TGHash< TDat > Class Template Reference

Graph Hash Table. More...

#include <ghash.h>

Collaboration diagram for TGHash< TDat >:
Collaboration graph
[legend]

List of all members.

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.
 TGHash (TSIn &SIn)
void Save (TSOut &SOut) const
const TDat & operator[] (const int &KeyId) const
 Accesses the data at hash table position index KeyId.
TDat & operator[] (const int &KeyId)
 Accesses the data at hash table position index KeyId.
const TDat & operator() (const TGraphKey &Key) const
 Accesses the data of graph-key Key.
TDat & operator() (const TGraphKey &Key)
 Accesses the data of graph-key Key.
TIter BegI () const
 Returns iterator to the first element of the hash table.
TIter EndI () const
 Returns iterator to one past the last element of the hash table.
TIter GetI (const int &KeyId) const
 Returns iterator to a key at position index KeyId.
bool HashTrees () const
 Returns whether the hash table only hashes trees and not arbitrary directed graphs.
void Gen (const int &ExpectVals)
 Initializes the hash table for the expected number of keys ExpectVals.
void Clr (const bool &DoDel=true, const int &NoDelLim=-1)
 Removes all the elements from the hash table.
bool Empty () const
 Tests whether the hash table is empty.
int Len () const
 Returns the number of keys in the hash table.
int GetPorts () const
 Returns the number of ports in the hash table.
bool IsAutoSize () const
 Tests whether the hash table automatically adjusts the number of ports based on the number of keys.
int GetMxKeyIds () const
 Returns the maximum key Id of any element in the hash table.
bool IsKeyIdEqKeyN () const
 Tests whether there are any unused slots in the hash table.
int AddKey (const PNGraph &Graph)
 Adds a key Graph to the table and returns its KeyId.
TDat & AddDat (const PNGraph &Graph)
 Adds a key Graph to the table and returns its data value.
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.
bool IsKey (const PNGraph &Graph) const
 Test whether Graph is an existing key in the hash table.
int GetKeyId (const PNGraph &Graph) const
 Returns the KeyId (position index) of key Graph.
const TDat & GetDat (const PNGraph &Graph) const
 Returns the data associated with key Graph.
TDat & GetDat (const PNGraph &Graph)
 Returns the data associated with key Graph.
const TGraphKey & GetKey (const int &KeyId) const
 Returns the GraphKey with position index KeyId.
int GetKeyId (const TGraphKey &Key) const
 Returns the KeyId for a given Key.
bool IsKey (const TGraphKey &Key) const
 Tests whether a given Key exists in the hash table.
bool IsKey (const TGraphKey &Key, int &KeyId) const
 Tests whether a given Key exists in the hash table.
bool IsKeyId (const int &KeyId) const
 Tests whether there exists a key at given position index KeyId.
const TDat & GetDat (const TGraphKey &Key) const
 Returns data with a given graph Key.
TDat & GetDat (const TGraphKey &Key)
 Returns data with a given graph Key.
const TDat & GetDatId (const int &KeyId) const
 Returns data at a given position index KeyId.
TDat & GetDatId (const int &KeyId)
 Returns data at a given position index KeyId.
void GetKeyDat (const int &KeyId, TGraphKey &Key, TDat &Dat) const
 Returns Key and Data at a given position index KeyId.
bool IsKeyGetDat (const TGraphKey &Key, TDat &Dat) const
 Test whether Key exists and sets its data to Dat.
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.
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.
int FFirstKeyId () const
 Finds first KeyId.
bool FNextKeyId (int &KeyId) const
 Finds next KeyId.
void GetKeyV (TVec< TGraphKey > &KeyV) const
 Returns a vector of keys stored in the hash table.
void GetDatV (TVec< TDat > &DatV) const
 Returns a vector of data elements stored in the hash table.
void GetKeyIdByDat (TIntV &KeyIdV, const bool &Asc=true) const
 Returns a vector of KeyIds of hash table elements sorted by their data value.
void GetKeyIdByGSz (TIntV &KeyIdV, const bool &Asc=true) const
 Returns a vector of KeyIds of hash table elements sorted by their graph size.
void GetKeyDatPrV (TVec< TPair< TGraphKey, TDat > > &KeyDatPrV) const
 Returns a vector of pairs (Key, Data) elements stored in the hash table.
void GetDatKeyPrV (TVec< TPair< TDat, TGraphKey > > &DatKeyPrV) const
 Returns a vector of pairs (Data, Key) elements stored in the hash table.
void Defrag ()
 Removes unused slots from the hash table.
void Pack ()
 Frees the unused memory by the hash table.
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.
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.
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.
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.

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: