SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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:548
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:503
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:1137
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:400
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
Definition: bd.h:196
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:479
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:974
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