SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
ghash.h
Go to the documentation of this file.
1 //#//////////////////////////////////////////////
3 
7 class TGraphKey {
8 public:
9  static const int RoundTo;
10 private:
11 public:
13  TIntPrV EdgeV; // renumbers the graph (node Ids 0..nodes-1)
14  TFltV SigV; // signature (for hashing)
15  TInt VariantId; // graphs can have the same signature but are not-isomorphic. VariantId starts with 1.
16 public:
17  TGraphKey() : Nodes(-1), EdgeV(), SigV(), VariantId(0) { }
18  TGraphKey(const TSFltV& GraphSigV);
19  TGraphKey(const TIntV& GraphSigV);
20  TGraphKey(const TFltV& GraphSigV);
21  TGraphKey(const TGraphKey& GraphKey);
22  TGraphKey(TSIn& SIn);
23  void Save(TSOut& SOut) const;
24  TGraphKey& operator = (const TGraphKey& GraphKey);
25  bool operator == (const TGraphKey& GraphKey) const { return SigV==GraphKey.SigV && VariantId==GraphKey.VariantId; }
26 
27  int GetPrimHashCd() const { return abs(SigV.GetPrimHashCd() ^ VariantId); }
28  int GetSecHashCd() const { return abs(SigV.GetSecHashCd() ^ VariantId<<8); }
29 
31  int GetNodes() const { return Nodes; }
33  int GetEdges() const { return EdgeV.Len(); }
35 
40  int GetSigLen() const { return SigV.Len(); }
42 
45  int GetVariant() const { return VariantId; }
47  void SetVariant(const int& Variant) { VariantId = Variant; }
49  void SetEdgeV(const TIntPrV& EdgeIdV) { EdgeV = EdgeIdV; }
50 
52  PNGraph GetNGraph() const;
54 
56  void TakeGraph(const PNGraph& Graph);
58 
61  void TakeGraph(const PNGraph& Graph, TIntPrV& NodeMap);
63 
65  void TakeSig(const PNGraph& Graph, const int& MnSvdGraph, const int& MxSvdGraph);
66 
68  void SaveTxt(FILE *F) const;
70 
72  void SaveGViz(const TStr& OutFNm, const TStr& Desc = TStr(), const TStr& NodeAttrs="", const int& Size=-1) const;
74 
76  void DrawGViz(const TStr& OutFNm, const TStr& Desc = TStr(), const TStr& NodeAttrs="", const int& Size=-1) const;
77 
79 
82  static bool IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TIntV& NodeIdMap);
84  static bool IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TVec<TIntV>& NodeIdMapV);
86  static bool IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TVec<TIntV>& NodeIdMapV, int& IsoPermId);
87 };
88 
89 //#//////////////////////////////////////////////
91 
102 template <class TDat>
103 class TGHash {
104 public:
106 private:
107  TInt MxIsoCheck; // maximum graph size for which we perform brute force graph isomorphism check
108  TInt MxSvdGraph; // maximum graph size for which we perform SVD-based approximate isomorphism check
109  THash<TInt, TVec<TIntV> > GSzToPermH; // Graph size to a vector of all node permutations (for graphs of up to MxIsoCkeck nodes)
110  TBool HashOnlyTrees; // hashing only trees (exact isomorphism test)
112 private:
113  void InitPermutations();
114  int IsGetKeyId(const PNGraph& Graph) const;
115  int IsGetKeyId(const PNGraph& Graph, TGraphKey& GKey) const;
116  int IsGetKeyId(const PNGraph& Graph, TGraphKey& GKey, TIntPrV& NodeMap) const;
117 public:
119 
126  TGHash(const bool& HashTrees, const int& MaxIsoCheck=8, const int& MaxSvdGraph=500);
127  TGHash(TSIn& SIn);
128  void Save(TSOut& SOut) const;
129 
131  const TDat& operator [] (const int& KeyId) const { return GraphH[KeyId]; }
133  TDat& operator [] (const int& KeyId) { return GraphH[KeyId]; }
135  const TDat& operator () (const TGraphKey& Key) const { return GraphH.GetDat(Key); }
137  TDat& operator () (const TGraphKey& Key) { return GraphH.GetDat(Key); }
139  TIter BegI() const { return GraphH.BegI(); }
141  TIter EndI() const { return GraphH.EndI(); }
143  TIter GetI(const int& KeyId) const { return GraphH.GetI(KeyId); }
144 
146  bool HashTrees() const { return HashOnlyTrees; }
147 
149  void Gen(const int& ExpectVals) { GraphH.Gen(ExpectVals); }
151 
154  void Clr(const bool& DoDel=true, const int& NoDelLim=-1) { GraphH.Clr(DoDel, NoDelLim); }
156  bool Empty() const { return GraphH.Empty(); }
158  int Len() const { return GraphH.Len(); }
160  int GetPorts() const { return GraphH.GetPorts(); }
162  bool IsAutoSize() const { return GraphH.IsAutoSize(); }
164  int GetMxKeyIds() const { return GraphH.GetMxKeyIds(); }
166 
168  bool IsKeyIdEqKeyN() const { return GraphH.IsKeyIdEqKeyN(); }
169 
171 
173  int AddKey(const PNGraph& Graph);
175 
177  TDat& AddDat(const PNGraph& Graph) { return GraphH[AddKey(Graph)]; }
179 
181  TDat& AddDat(const PNGraph& Graph, const TDat& Dat) { return GraphH[AddKey(Graph)] = Dat; }
182 
184  bool IsKey(const PNGraph& Graph) const { int k=IsGetKeyId(Graph); return k!=-1; }
186 
188  int GetKeyId(const PNGraph& Graph) const { return IsGetKeyId(Graph); }
190 
192  const TDat& GetDat(const PNGraph& Graph) const { return GraphH[GetKeyId(Graph)]; }
194 
196  TDat& GetDat(const PNGraph& Graph) { return GraphH[GetKeyId(Graph)]; }
197 
199  const TGraphKey& GetKey(const int& KeyId) const { return GraphH.GetKey(KeyId); }
201 
203  int GetKeyId(const TGraphKey& Key) const { return GraphH.GetKeyId(Key); }
205  bool IsKey(const TGraphKey& Key) const { return GraphH.IsKey(Key); }
207  bool IsKey(const TGraphKey& Key, int& KeyId) const { return GraphH.IsKey(Key, KeyId); }
209  bool IsKeyId(const int& KeyId) const { return GraphH.IsKeyId(KeyId); }
211 
213  const TDat& GetDat(const TGraphKey& Key) const { return GraphH.GetDat(Key); }
215 
217  TDat& GetDat(const TGraphKey& Key) { return GraphH.GetDat(Key); }
219 
221  const TDat& GetDatId(const int& KeyId) const { return GraphH[KeyId]; }
223 
225  TDat& GetDatId(const int& KeyId) { return GraphH[KeyId]; }
226 
228  void GetKeyDat(const int& KeyId, TGraphKey& Key, TDat& Dat) const { GraphH.GetKeyDat(KeyId, Key, Dat); }
230  bool IsKeyGetDat(const TGraphKey& Key, TDat& Dat) const { return GraphH.IsKeyGetDat(Key, Dat); }
231 
233 
235  bool GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV) const;
237 
239  bool GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV, int& KeyId) const;
240 
242 
245  int FFirstKeyId() const { return 0-1; }
247 
250  bool FNextKeyId(int& KeyId) const { return GraphH.FNextKeyId(KeyId); }
252  void GetKeyV(TVec<TGraphKey>& KeyV) const { GraphH.GetKeyV(KeyV); }
254  void GetDatV(TVec<TDat>& DatV) const { GraphH.GetDatV(DatV); }
256 
258  void GetKeyIdByDat(TIntV& KeyIdV, const bool& Asc = true) const;
260 
263  void GetKeyIdByGSz(TIntV& KeyIdV, const bool& Asc = true) const;
265  void GetKeyDatPrV(TVec<TPair<TGraphKey, TDat> >& KeyDatPrV) const { GraphH.GetKeyDatPrV(KeyDatPrV); }
267  void GetDatKeyPrV(TVec<TPair<TDat, TGraphKey> >& DatKeyPrV) const { GraphH.GetDatKeyPrV(DatKeyPrV); }
268 
270 
272  void Defrag() { GraphH.Defrag(); }
274  void Pack() { GraphH.Pack(); }
275 
277  void DrawGViz(const int& KeyId, const TStr& OutFNmPref, const TStr& OutputType = "gif", TStr Desc="") const;
279  void DrawGViz(const TIntV& KeyIdV, const TStr& OutFNmPref, const TStr& OutputType = "gif") const;
281  void SaveTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm, const bool& SortByKeyVal=true) const;
283  void SaveDetailTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm) const;
284 };
285 
286 template <class TDat>
288  GSzToPermH.Clr();
289  for (int nodes = 2; nodes <= MxIsoCheck; nodes++) {
290  TVec<TIntV> NodePermutationV;
291  TIntV NodeIdV(nodes, 0);
292  for (int i = 0; i < nodes; i++) NodeIdV.Add(i);
293  NodeIdV.Pack();
294  NodePermutationV.Add(NodeIdV);
295  while (NodeIdV.NextPerm()) {
296  NodePermutationV.Add(NodeIdV);
297  }
298  NodePermutationV.Pack();
299  GSzToPermH.AddDat(nodes, NodePermutationV);
300  }
301 }
302 
303 template <class TDat>
304 TGHash<TDat>::TGHash(const bool& HashTrees, const int& MaxIsoCheck, const int& MaxSvdGraph) :
305  MxIsoCheck(MaxIsoCheck), MxSvdGraph(MaxSvdGraph), GSzToPermH(), HashOnlyTrees(HashTrees), GraphH() {
306  if (! HashTrees) {
308  }
309 }
310 
311 template <class TDat>
312 TGHash<TDat>::TGHash(TSIn& SIn) : MxIsoCheck(SIn), MxSvdGraph(SIn), GSzToPermH(), HashOnlyTrees(SIn), GraphH(SIn) {
313  if (! HashOnlyTrees) {
315  }
316 }
317 
318 template <class TDat>
319 void TGHash<TDat>::Save(TSOut& SOut) const {
320  MxIsoCheck.Save(SOut);
321  MxSvdGraph.Save(SOut);
322  HashOnlyTrees.Save(SOut);
323  GraphH.Save(SOut);
324 }
325 
326 template <class TDat>
327 int TGHash<TDat>::AddKey(const PNGraph& Graph) {
328  if (HashOnlyTrees) {
329  int RootNId; IAssert(TSnap::IsTree(Graph, RootNId));
330  TIntV TreeSig; TSnap::GetTreeSig(Graph, RootNId, TreeSig);
331  TGraphKey GKey(TreeSig);
332  const int KeyId = GraphH.GetKeyId(GKey);
333  if (KeyId == -1) {
334  GKey.TakeGraph(Graph);
335  return GraphH.AddKey(GKey);
336  }
337  return KeyId;
338  } else {
339  TGraphKey GKey;
340  GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph); // get signature
341  const int Nodes = GKey.GetNodes();
342  if (Nodes > 2 && Nodes <= MxIsoCheck) {
343  GKey.TakeGraph(Graph);
344  // Check all variants with same signature
345  for (int variant = 1; ; variant++) {
346  GKey.SetVariant(variant);
347  int KeyId = GraphH.GetKeyId(GKey);
348  if (KeyId == -1) { // Key of such signature and variant does not exist yet.
349  KeyId = GraphH.AddKey(GKey);
350  return KeyId;
351  }
352  if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes))) { // Graph isomorphism test
353  return KeyId; // Found isomorphic graph.
354  }
355  }
356  } else {
357  const int KeyId = GraphH.GetKeyId(GKey);
358  if (KeyId == -1) {
359  GKey.TakeGraph(Graph);
360  return GraphH.AddKey(GKey);
361  }
362  return KeyId;
363  }
364  }
365  Fail;
366  return -1;
367 }
368 
369 template <class TDat>
370 int TGHash<TDat>::IsGetKeyId(const PNGraph& Graph) const {
371  TGraphKey GKey;
372  return IsGetKeyId(Graph, GKey);
373 }
374 
375 template <class TDat>
376 int TGHash<TDat>::IsGetKeyId(const PNGraph& Graph, TGraphKey& GKey) const {
377  if (HashOnlyTrees) {
378  // For trees we perform exact isomorshism test based on graph signatures
379  int RootNId; IAssert(TSnap::IsTree(Graph, RootNId));
380  TIntV TreeSig; TSnap::GetTreeSig(Graph, RootNId, TreeSig);
381  GKey = TGraphKey(TreeSig);
382  const int KeyId = GraphH.GetKeyId(GKey);
383  return KeyId;
384  } else {
385  // For small graphs of less than MxIsoCheck nodes we perform brute force isomorphism checking
386  GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph);
387  const int Nodes = GKey.GetNodes();
388  if (Nodes > 2 && Nodes <= MxIsoCheck) {
389  GKey.TakeGraph(Graph);
390  for (int variant = 1; ; variant++) {
391  GKey.SetVariant(variant);
392  int KeyId = GraphH.GetKeyId(GKey); // Is there a graph of the same signature and same VariantId
393  if (KeyId == -1) { return -1; }
394  if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes))) { return KeyId; } // perform brute force isomorphism check
395  }
396  } else {
397  // For all other graphs we perform approximate graph isomorphism checking
398  const int KeyId = GraphH.GetKeyId(GKey);
399  return KeyId;
400  }
401  }
402  Fail;
403  return -1;
404 }
405 
406 template <class TDat>
407 bool TGHash<TDat>::GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV) const {
408  int KeyId;
409  return GetNodeMap(Graph, NodeMapV, KeyId);
410 }
411 
412 template <class TDat>
413 bool TGHash<TDat>::GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV, int& KeyId) const {
414  NodeMapV.Clr(false);
415  if (HashOnlyTrees) {
416  int RootNId; IAssert(TSnap::IsTree(Graph, RootNId));
417  TIntV TreeSig; TSnap::GetTreeSig(Graph, RootNId, TreeSig, NodeMapV);
418  TGraphKey GKey(TreeSig);
419  KeyId = GraphH.GetKeyId(GKey);
420  return KeyId != -1;
421  } else {
422  const int Nodes = Graph->GetNodes();
423  int IsoPermId = -1;
424  NodeMapV.Clr(false);
425  if (Nodes == 0) { return true; }
426  else if (Nodes == 1) {
427  NodeMapV.Add(TIntPr(Graph->BegNI().GetId(), 0)); return true; }
428  else if (Nodes <= MxIsoCheck) {
429  TGraphKey GKey;
430  GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph);
431  GKey.TakeGraph(Graph, NodeMapV);
432  for (int variant = 1; ; variant++) {
433  GKey.SetVariant(variant);
434  KeyId = GraphH.GetKeyId(GKey);
435  if (KeyId == -1) { return false; }
436  if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes), IsoPermId)) {
437  const TIntV& K1K2Perm = GSzToPermH.GetDat(Nodes)[IsoPermId];
438  // map from graph to key1 to key2
439  for (int i = 0; i < NodeMapV.Len(); i++) {
440  NodeMapV[i].Val2 = K1K2Perm[NodeMapV[i].Val2]; }
441  return true;
442  }
443  }
444  return false;
445  } else {
446  return false; // graph too big to find the mapping
447  }
448  }
449  Fail;
450  return false;
451 }
452 
453 template <class TDat>
454 void TGHash<TDat>::GetKeyIdByDat(TIntV& KeyIdV, const bool& Asc) const {
455  TVec<TQuad<TDat, TInt,TInt, TInt> > DatKeyIdV(Len(), 0); // <TDat,Nodes,Edges,KeyId>
456  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
457  DatKeyIdV.Add(TQuad<TDat, TInt,TInt, TInt>(GetDatId(i), GetKey(i).GetNodes(), GetKey(i).GetEdges(), i));
458  }
459  DatKeyIdV.Sort(Asc);
460  KeyIdV.Gen(Len(), 0);
461  for (int i = 0; i < Len(); i++) {
462  KeyIdV.Add(DatKeyIdV[i].Val4);
463  }
464 }
465 
466 template <class TDat>
467 void TGHash<TDat>::GetKeyIdByGSz(TIntV& KeyIdV, const bool& Asc) const {
468  TVec<TQuad<TInt,TInt, TDat, TInt> > DatKeyIdV(Len(), 0); // <Nodes,Edges,TDat,KeyId>
469  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
470  DatKeyIdV.Add(TQuad< TInt,TInt, TDat, TInt>(GetKey(i).GetNodes(), GetKey(i).GetEdges(), GetDatId(i), i));
471  }
472  DatKeyIdV.Sort(Asc);
473  KeyIdV.Gen(Len(), 0);
474  for (int i = 0; i < Len(); i++) {
475  KeyIdV.Add(DatKeyIdV[i].Val4);
476  }
477 }
478 
479 template <class TDat>
480 void TGHash<TDat>::DrawGViz(const int& KeyId, const TStr& OutFNmPref, const TStr& OutputType, TStr Desc) const {
481  IAssert(OutputType == "ps" || OutputType == "gif" || OutputType == "png");
482  const TGraphKey& GKey = GetKey(KeyId);
483  const TStr Desc1 = TStr::Fmt("%s (%d, %d)", Desc.CStr(), GKey.GetNodes(), GKey.GetEdges());
484  GKey.SaveGViz(OutFNmPref+".dot", Desc1);
485  TSnap::TSnapDetail::GVizDoLayout(OutFNmPref+".dot", OutFNmPref+"."+OutputType, gvlDot);
486 }
487 
488 template <class TDat>
489 void TGHash<TDat>::DrawGViz(const TIntV& KeyIdV, const TStr& OutFNmPref, const TStr& OutputType) const {
490  IAssert(OutputType == "ps" || OutputType == "gif" || OutputType == "png");
491  TExeTm ExeTm;
492  printf("Plotting %d graphs\n", KeyIdV.Len());
493  for (int i = 0; i < KeyIdV.Len(); i++) {
494  const TStr FNm = TStr::Fmt("%s.%03d.key%d.", OutFNmPref.CStr(), i+1, KeyIdV[i]());
495  const TStr Desc = TStr::Fmt("KeyId:%d", KeyIdV[i]());
496  const TGraphKey& GKey = GetKey(KeyIdV[i]);
497  printf("\r %d g(%d, %d) ", i, GKey.GetNodes(), GKey.GetEdges());
498  GKey.SaveGViz(FNm+"dot", Desc);
499  TSnap::TSnapDetail::GVizDoLayout(FNm+"dot", FNm+OutputType, gvlDot);
500  }
501  printf("done [%s].\n", ExeTm.GetTmStr());
502 }
503 
504 template <class TDat>
505 void TGHash<TDat>::SaveTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm, const bool& SortByKeyVal) const {
506  TIntV KeyIdV;
507  if (SortByKeyVal) GetKeyIdByDat(KeyIdV, false);
508  else GetKeyIdByGSz(KeyIdV, true);
509  FILE *F = fopen(OutFNm.CStr(), "wt");
510  fprintf(F, "Graph-Hash-Table");
511  fprintf(F, "%s\n", Desc.CStr());
512  fprintf(F, "%d graphs\n", KeyIdV.Len());
513  fprintf(F, "Rank\tKeyId\tNodes\tEdges\t%s\n", DatColNm.CStr());
514  for (int i = 0; i < KeyIdV.Len(); i++) {
515  const TGraphKey& Key = GetKey(KeyIdV[i]);
516  fprintf(F, "%d\t%d\t%d\t%d\t%s\n", i+1, KeyIdV[i](), Key.GetNodes(), Key.GetEdges(),
517  GetDatId(KeyIdV[i]).GetStr().CStr());
518  }
519  fclose(F);
520 }
521 
522 template <class TDat>
523 void TGHash<TDat>::SaveDetailTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm) const {
524  TIntV KeyIdV; GetKeyIdByDat(KeyIdV, false);
525  FILE *F = fopen(OutFNm.CStr(), "wt");
526  fprintf(F, "Graph-Hash-Table\n");
527  fprintf(F, "%s\n", Desc.CStr());
528  fprintf(F, "%d graphs", KeyIdV.Len());
529  for (int i = 0; i < KeyIdV.Len(); i++) {
530  fprintf(F, "\n\n[%5d]\tRank: %d\n", KeyIdV[i](), i+1);
531  fprintf(F, "Dat: %s\n", GetDat(KeyIdV[i]).GetStr().CStr());
532  GetDatId(KeyIdV[i]).SaveTxt(F);
533  }
534  fclose(F);
535 }
536 
537 //#//////////////////////////////////////////////
540 private:
542 public:
544  TSimpleGraph(const TIntPrV& GEdgeV) : EdgeV(GEdgeV) { }
545  bool operator == (const TSimpleGraph& Graph) const { return EdgeV == Graph.EdgeV; }
546  bool operator < (const TSimpleGraph& Graph) const { return EdgeV < Graph.EdgeV; }
547 
548  int GetEdges() const { return EdgeV.Len(); }
549  void AddEdge(const int& SrcNId, const int& DstNId) { EdgeV.Add(TIntPr(SrcNId, DstNId)); }
550  bool Join(const TSimpleGraph& G1, const TSimpleGraph& G2);
551  TIntPrV& GetEdgeV() { return EdgeV; }
552  TIntPrV& operator () () { return EdgeV; }
553 
554  void Dump(const TStr& Desc = TStr()) const;
555 };
557 
558 //#//////////////////////////////////////////////
561 private:
562  TSimpleGraphV SgV, NextSgV;
565 public:
566  TSubGraphsEnum(PNGraph Graph) : NGraph(Graph) { }
567 
568  void Gen2Graphs();
569  void EnumSubGraphs(const int& MaxEdges);
570  void RecurBfs(const int& MxDepth);
571  void RecurBfs(const int& NId, const int& Depth, TSimpleGraph& PrevG);
572  void RecurBfs1(const int& MxDepth);
573  void RecurBfs1(const int& NId, const int& Depth);
574  //void RecurBfs(const int& NId, const int& Depth, const THash<TIntPr, TInt>& EdgeH);
575 };
576 
577 
int GetEdges() const
Returns the number of edges in the graph.
Definition: ghash.h:33
void TakeSig(const PNGraph &Graph, const int &MnSvdGraph, const int &MxSvdGraph)
Creates a signature for a given directed graph.
Definition: ghash.cpp:94
int Len() const
Returns the number of keys in the hash table.
Definition: ghash.h:158
#define IAssert(Cond)
Definition: bd.h:262
TDat & GetDatId(const int &KeyId)
Returns data at a given position index KeyId.
Definition: ghash.h:225
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
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.
Definition: ghash.h:181
const TGraphKey & GetKey(const int &KeyId) const
Returns the GraphKey with position index KeyId.
Definition: ghash.h:199
Connected Sub-graph Enumeration.
Definition: ghash.h:560
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:999
TIter EndI() const
Returns iterator to one past the last element of the hash table.
Definition: ghash.h:141
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...
Definition: ghash.h:523
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...
Definition: ghash.h:407
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
void GetDatV(TVec< TDat > &DatV) const
Definition: hash.h:492
TBool HashOnlyTrees
Definition: ghash.h:110
Definition: tm.h:355
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...
Definition: ghash.h:480
void GetKeyDat(const int &KeyId, TGraphKey &Key, TDat &Dat) const
Returns Key and Data at a given position index KeyId.
Definition: ghash.h:228
TSimpleGraphV NextSgV
Definition: ghash.h:562
bool operator<(const TSimpleGraph &Graph) const
Definition: ghash.h:546
TSimpleGraph()
Definition: ghash.h:543
Simple directed/undirected graph defined by its edges.
Definition: ghash.h:539
TGHash(const bool &HashTrees, const int &MaxIsoCheck=8, const int &MaxSvdGraph=500)
Default contructor.
Definition: ghash.h:304
TFltV SigV
Definition: ghash.h:14
bool operator==(const TGraphKey &GraphKey) const
Definition: ghash.h:25
THash< TGraphKey, TDat >::TIter TIter
Definition: ghash.h:105
bool IsAutoSize() const
Tests whether the hash table automatically adjusts the number of ports based on the number of keys...
Definition: ghash.h:162
bool IsKeyId(const int &KeyId) const
Definition: hash.h:260
#define Fail
Definition: bd.h:238
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
void GetKeyIdByGSz(TIntV &KeyIdV, const bool &Asc=true) const
Returns a vector of KeyIds of hash table elements sorted by their graph size.
Definition: ghash.h:467
TIter BegI() const
Definition: hash.h:213
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TInt Nodes
Definition: ghash.h:12
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:1011
THash< TInt, TVec< TIntV > > GSzToPermH
Definition: ghash.h:109
bool Empty() const
Definition: hash.h:227
void Gen(const int &ExpectVals)
Initializes the hash table for the expected number of keys ExpectVals.
Definition: ghash.h:149
int GetPorts() const
Returns the number of ports in the hash table.
Definition: ghash.h:160
const TDat & GetDat(const PNGraph &Graph) const
Returns the data associated with key Graph.
Definition: ghash.h:192
bool FNextKeyId(int &KeyId) const
Finds next KeyId.
Definition: ghash.h:250
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
TIntPrV & GetEdgeV()
Definition: ghash.h:551
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TSimpleGraphV SgV
Definition: ghash.h:562
int GetEdges() const
Definition: ghash.h:548
TIter EndI() const
Definition: hash.h:218
bool Join(const TSimpleGraph &G1, const TSimpleGraph &G2)
Definition: ghash.cpp:233
Graph Hash Table.
Definition: ghash.h:103
static bool IsIsomorph(const TGraphKey &Key1, const TGraphKey &Key2, const TIntV &NodeIdMap)
Checks whether directed graph Key1 is isomorphic to the directed graph Key2 under node Id permutation...
Definition: ghash.cpp:186
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Removes all the elements from the hash table.
Definition: ghash.h:154
void GetDatKeyPrV(TVec< TPair< TDat, TKey > > &DatKeyPrV) const
Definition: hash.h:511
void EnumSubGraphs(const int &MaxEdges)
Definition: ghash.cpp:312
void GetTreeSig(const PGraph &Graph, const int &RootNId, TIntV &Sig)
Definition: alg.h:484
void Defrag()
Definition: hash.h:555
TVec< TSimpleGraph > TSimpleGraphV
Definition: ghash.h:556
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ghash.h:319
void AddEdge(const int &SrcNId, const int &DstNId)
Definition: ghash.h:549
const char * GetTmStr() const
Definition: tm.h:370
bool IsKeyGetDat(const TGraphKey &Key, TDat &Dat) const
Test whether Key exists and sets its data to Dat.
Definition: ghash.h:230
THash< TIntPr, TIntH > EdgeH
Definition: ghash.h:563
void GVizDoLayout(const TStr &GraphInFNm, TStr OutFNm, const TGVizLayout &Layout)
Runs GraphViz layout engine over a graph saved in the file GraphInFNm with output saved to OutFNm...
Definition: gviz.cpp:5
bool IsTree(const PGraph &Graph, int &RootNIdX)
Definition: alg.h:460
TGraphKey & operator=(const TGraphKey &GraphKey)
Definition: ghash.cpp:37
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
bool IsKeyIdEqKeyN() const
Tests whether there are any unused slots in the hash table.
Definition: ghash.h:168
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void Gen(const int &ExpectVals)
Definition: hash.h:222
bool NextPerm()
Generates next permutation of the elements in the vector.
Definition: ds.h:1368
bool IsKey(const PNGraph &Graph) const
Test whether Graph is an existing key in the hash table.
Definition: ghash.h:184
void RecurBfs(const int &MxDepth)
Definition: ghash.cpp:345
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
static const int RoundTo
Definition: ghash.h:9
const TDat & operator()(const TGraphKey &Key) const
Accesses the data of graph-key Key.
Definition: ghash.h:135
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int GetVariant() const
Returns the graph variant Id.
Definition: ghash.h:45
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TIntPrV & operator()()
Definition: ghash.h:552
const TDat & GetDat(const TGraphKey &Key) const
Returns data with a given graph Key.
Definition: ghash.h:213
TIntPrV EdgeV
Definition: ghash.h:541
void Dump(const TStr &Desc=TStr()) const
Definition: ghash.cpp:274
TInt MxIsoCheck
Definition: ghash.h:107
bool operator==(const TSimpleGraph &Graph) const
Definition: ghash.h:545
TGraphKey()
Definition: ghash.h:17
TDat & AddDat(const PNGraph &Graph)
Adds a key Graph to the table and returns its data value.
Definition: ghash.h:177
int GetSigLen() const
Returns the length of the signature vector of a graph.
Definition: ghash.h:40
TInt MxSvdGraph
Definition: ghash.h:108
void Save(TSOut &SOut) const
Definition: ghash.cpp:32
Definition: gviz.h:3
TIntPrV EdgeV
Definition: ghash.h:13
void TakeGraph(const PNGraph &Graph)
Creates a key from a given directed graph.
Definition: ghash.cpp:58
Definition: fl.h:128
int GetMxKeyIds() const
Definition: hash.h:231
TIter BegI() const
Returns iterator to the first element of the hash table.
Definition: ghash.h:139
Definition: dt.h:1134
int GetNodes() const
Returns the number of nodes in the graph.
Definition: ghash.h:31
bool IsKey(const TGraphKey &Key, int &KeyId) const
Tests whether a given Key exists in the hash table.
Definition: ghash.h:207
void Pack()
Frees the unused memory by the hash table.
Definition: ghash.h:274
const TDat & GetDatId(const int &KeyId) const
Returns data at a given position index KeyId.
Definition: ghash.h:221
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
void GetKeyDatPrV(TVec< TPair< TGraphKey, TDat > > &KeyDatPrV) const
Returns a vector of pairs (Key, Data) elements stored in the hash table.
Definition: ghash.h:265
void Defrag()
Removes unused slots from the hash table.
Definition: ghash.h:272
PNGraph GetNGraph() const
Returns the directed graph stored in the GraphKey object.
Definition: ghash.cpp:47
int FFirstKeyId() const
Finds first KeyId.
Definition: ghash.h:245
Definition: ds.h:32
void SaveGViz(const TStr &OutFNm, const TStr &Desc=TStr(), const TStr &NodeAttrs="", const int &Size=-1) const
Saves the graph to the .DOT file format used by GraphViz.
Definition: ghash.cpp:154
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.
Definition: ghash.h:505
TInt VariantId
Definition: ghash.h:15
int GetId() const
Returns ID of the current node.
Definition: graph.h:396
Small Directed Graphs.
Definition: ghash.h:7
bool Empty() const
Tests whether the hash table is empty.
Definition: ghash.h:156
int IsGetKeyId(const PNGraph &Graph) const
Definition: ghash.h:370
int GetSecHashCd() const
Definition: ghash.h:28
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
void SetEdgeV(const TIntPrV &EdgeIdV)
Returns a vector of directed edges of a graph.
Definition: ghash.h:49
Definition: dt.h:412
int GetMxKeyIds() const
Returns the maximum key Id of any element in the hash table.
Definition: ghash.h:164
Definition: ds.h:219
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
void Gen2Graphs()
Definition: ghash.cpp:282
bool IsKeyId(const int &KeyId) const
Tests whether there exists a key at given position index KeyId.
Definition: ghash.h:209
int GetPorts() const
Definition: hash.h:229
TSubGraphsEnum(PNGraph Graph)
Definition: ghash.h:566
Definition: hash.h:97
int GetPrimHashCd() const
Definition: ghash.h:27
void RecurBfs1(const int &MxDepth)
Definition: ghash.cpp:386
void GetDatKeyPrV(TVec< TPair< TDat, TGraphKey > > &DatKeyPrV) const
Returns a vector of pairs (Data, Key) elements stored in the hash table.
Definition: ghash.h:267
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
int GetKeyId(const PNGraph &Graph) const
Returns the KeyId (position index) of key Graph.
Definition: ghash.h:188
THash< TGraphKey, TDat > GraphH
Definition: ghash.h:111
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
bool IsKey(const TGraphKey &Key) const
Tests whether a given Key exists in the hash table.
Definition: ghash.h:205
void SetVariant(const int &Variant)
Sets the Variant Id of a given graph.
Definition: ghash.h:47
void DrawGViz(const TStr &OutFNm, const TStr &Desc=TStr(), const TStr &NodeAttrs="", const int &Size=-1) const
Saves the graph to the .DOT file format and calls GraphViz to draw it.
Definition: ghash.cpp:180
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
bool HashTrees() const
Returns whether the hash table only hashes trees and not arbitrary directed graphs.
Definition: ghash.h:146
const TDat & operator[](const int &KeyId) const
Accesses the data at hash table position index KeyId.
Definition: ghash.h:131
int AddKey(const PNGraph &Graph)
Adds a key Graph to the table and returns its KeyId.
Definition: ghash.h:327
void InitPermutations()
Definition: ghash.h:287
void SaveTxt(FILE *F) const
Saves the graph as a list of edges.
Definition: ghash.cpp:147
TIter GetI(const int &KeyId) const
Returns iterator to a key at position index KeyId.
Definition: ghash.h:143
char * CStr()
Definition: dt.h:476
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void GetKeyIdByDat(TIntV &KeyIdV, const bool &Asc=true) const
Returns a vector of KeyIds of hash table elements sorted by their data value.
Definition: ghash.h:454
Definition: dt.h:971
TDat & GetDat(const TGraphKey &Key)
Returns data with a given graph Key.
Definition: ghash.h:217
int Len() const
Definition: hash.h:228
bool IsAutoSize() const
Definition: hash.h:230
int GetKeyId(const TGraphKey &Key) const
Returns the KeyId for a given Key.
Definition: ghash.h:203
void GetDatV(TVec< TDat > &DatV) const
Returns a vector of data elements stored in the hash table.
Definition: ghash.h:254
void Pack()
Definition: hash.h:289
TDat & GetDat(const PNGraph &Graph)
Returns the data associated with key Graph.
Definition: ghash.h:196
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
void GetKeyV(TVec< TGraphKey > &KeyV) const
Returns a vector of keys stored in the hash table.
Definition: ghash.h:252
PNGraph NGraph
Definition: ghash.h:564
TIter GetI(const TKey &Key) const
Definition: hash.h:220
TSimpleGraph(const TIntPrV &GEdgeV)
Definition: ghash.h:544