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.cpp
Go to the documentation of this file.
1 // Graph Hash Table Key
3 const int TGraphKey::RoundTo = 4; // round to 4 decimal places
4 
5 TGraphKey::TGraphKey(const TSFltV& GraphSigV) : Nodes(-1), EdgeV(), SigV(), VariantId(0) {
6  SigV.Gen(GraphSigV.Len());
7  for (int i = 0; i < GraphSigV.Len(); i++) {
8  SigV[i] = TFlt(TMath::Round(GraphSigV[i], RoundTo));
9  }
10 }
11 
12 TGraphKey::TGraphKey(const TIntV& GraphSigV) : Nodes(-1), EdgeV(), SigV(), VariantId(0) {
13  SigV.Gen(GraphSigV.Len());
14  for (int i = 0; i < GraphSigV.Len(); i++) {
15  SigV[i] = TFlt(GraphSigV[i]());
16  }
17 }
18 
19 TGraphKey::TGraphKey(const TFltV& GraphSigV) : Nodes(-1), EdgeV(), SigV(), VariantId(0) {
20  SigV.Gen(GraphSigV.Len());
21  for (int i = 0; i < GraphSigV.Len(); i++) {
22  SigV[i] = TFlt(TMath::Round(GraphSigV[i], RoundTo));
23  }
24 }
25 
26 TGraphKey::TGraphKey(const TGraphKey& GraphKey) : Nodes(GraphKey.Nodes),
27  EdgeV(GraphKey.EdgeV), SigV(GraphKey.SigV), VariantId(GraphKey.VariantId) {
28 }
29 
30 TGraphKey::TGraphKey(TSIn& SIn) : Nodes(SIn), EdgeV(SIn), SigV(SIn), VariantId(SIn) { }
31 
32 void TGraphKey::Save(TSOut& SOut) const {
33  Nodes.Save(SOut); EdgeV.Save(SOut);
34  SigV.Save(SOut); VariantId.Save(SOut);
35 }
36 
38  if (this != &GraphKey) {
39  Nodes = GraphKey.Nodes;
40  EdgeV = GraphKey.EdgeV;
41  SigV = GraphKey.SigV;
42  VariantId = GraphKey.VariantId;
43  }
44  return *this;
45 }
46 
48  PNGraph G = TNGraph::New();
49  for (int i = 0; i < GetNodes(); i++) G->AddNode(i);
50  for (int e = 0; e < GetEdges(); e++) {
51  G->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2);
52  }
53  G->Defrag();
54  return G;
55 }
56 
57 // renumbers nodes
58 void TGraphKey::TakeGraph(const PNGraph& Graph) {
59  TIntH NodeIdH;
60  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
61  NodeIdH.AddKey(NI.GetId()); }
62  Nodes = Graph->GetNodes();
63  EdgeV.Gen(Nodes, 0);
64  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
65  const int NewNId = NodeIdH.GetKeyId(NI.GetId());
66  for (int i = 0; i < NI.GetOutDeg(); i++) {
67  EdgeV.Add(TIntPr(NewNId, NodeIdH.GetKeyId(NI.GetOutNId(i))));
68  }
69  }
70  EdgeV.Sort(true);
71  EdgeV.Pack();
72 }
73 
74 void TGraphKey::TakeGraph(const PNGraph& Graph, TIntPrV& NodeMap) {
75  TIntSet NodeIdH;
76  int n = 0;
77  NodeMap.Gen(Graph->GetNodes(), 0);
78  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++, n++) {
79  NodeIdH.AddKey(NI.GetId());
80  NodeMap.Add(TIntPr(NI.GetId(), n));
81  }
82  Nodes = Graph->GetNodes();
83  EdgeV.Gen(Nodes, 0);
84  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
85  const int NewNId = NodeIdH.GetKeyId(NI.GetId());
86  for (int i = 0; i < NI.GetOutDeg(); i++) {
87  EdgeV.Add(TIntPr(NewNId, NodeIdH.GetKeyId(NI.GetOutNId(i))));
88  }
89  }
90  EdgeV.Sort(true);
91  EdgeV.Pack();
92 }
93 
94 void TGraphKey::TakeSig(const PNGraph& Graph, const int& MnSvdGraph, const int& MxSvdGraph) {
95  const int Edges = Graph->GetEdges();
96  Nodes = Graph->GetNodes();
97  VariantId = 0;
98  SigV.Gen(2+Nodes, 0);
99  // degree sequence
100  TIntPrV DegV(Nodes, 0);
101  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
102  DegV.Add(TIntPr(NodeI.GetInDeg(), NodeI.GetOutDeg()));
103  }
104  DegV.Sort(false);
105  // compose the signature: nodes, edges, sorted in- and out- degree sequence
106  SigV.Add(TFlt(Nodes));
107  SigV.Add(TFlt(Edges));
108  for (int i = 0; i < DegV.Len(); i++) {
109  SigV.Add(DegV[i].Val1());
110  SigV.Add(DegV[i].Val2());
111  }
112  // singular values signature
113  // it turns out that it is cheaper to do brute force isomorphism
114  // checking than to calculate SVD and then check isomorphism
115  if (Nodes >= MnSvdGraph && Nodes < MxSvdGraph) {
116  // perform full SVD
117  TFltVV AdjMtx(Nodes+1, Nodes+1);
118  TFltV SngValV;
119  TFltVV LSingV, RSingV;
120  TIntH NodeIdH;
121  // create adjecency matrix
122  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
123  NodeIdH.AddKey(NodeI.GetId());
124  }
125  for (TNGraph::TNodeI NodeI = Graph->BegNI(); NodeI < Graph->EndNI(); NodeI++) {
126  const int NodeId = NodeIdH.GetKeyId(NodeI.GetId()) + 1;
127  for (int e = 0; e < NodeI.GetOutDeg(); e++) {
128  const int DstNId = NodeIdH.GetKeyId(NodeI.GetOutNId(e)) + 1; // no self edges
129  if (NodeId != DstNId) AdjMtx.At(NodeId, DstNId) = 1;
130  }
131  }
132  try { // can fail to converge but results seem to be good
133  TSvd::Svd(AdjMtx, LSingV, SngValV, RSingV);
134  } catch(...) {
135  printf("\n***No SVD convergence: G(%d, %d): SngValV.Len():%d\n", Nodes(), Graph->GetEdges(), SngValV.Len());
136  }
137  // round singular values
138  SngValV.Sort(false);
139  for (int i = 0; i < SngValV.Len(); i++) {
140  SigV.Add(TMath::Round(SngValV[i], RoundTo));
141  }
142  }
143  //printf("SIG:\n"); for (int i = 0; i < SigV.Len(); i++) { printf("\t%f\n", SigV[i]); }
144  SigV.Pack();
145 }
146 
147 void TGraphKey::SaveTxt(FILE *F) const {
148  fprintf(F, "#GraphKey. Nodes: %d. Edges: %d\n", GetNodes(), GetEdges());
149  for (int i = 0; i < EdgeV.Len(); i++) {
150  fprintf(F," %d\t%d\n", EdgeV[i].Val1(), EdgeV[i].Val2());
151  }
152 }
153 
154 void TGraphKey::SaveGViz(const TStr& OutFNm, const TStr& Desc, const TStr& NodeAttrs, const int& Size) const {
155  FILE *F = fopen(OutFNm.CStr(), "wt");
156  fprintf(F, "/*****\n");
157  fprintf(F, " Graph (%d, %d)\n", GetNodes(), GetEdges());
158  //if (! Desc.Empty()) fprintf(F, " %s\n", Desc.CStr());
159  fprintf(F, "*****/\n\n");
160  fprintf(F, "digraph G {\n");
161  if (Size != -1) fprintf(F, " size=\"%d,%d\";\n", Size, Size);
162  fprintf(F, " graph [splines=true overlap=false]\n"); //size=\"12,10\" ratio=fill
163  if (NodeAttrs.Empty()) fprintf(F, " node [shape=ellipse, width=0.3, height=0.3]\n");
164  else fprintf(F, " node [shape=ellipse, %s]\n", NodeAttrs.CStr());
165  if (! EdgeV.Empty()) {
166  for (int e = 0; e < EdgeV.Len(); e++) {
167  fprintf(F, " %d -> %d;\n", EdgeV[e].Val1(), EdgeV[e].Val2()); }
168  } else {
169  for (int n = 0; n < Nodes; n++) { fprintf(F, " %d;\n", n); }
170  }
171  if (! Desc.Empty()) {
172  fprintf(F, " label = \"\\n%s\\n\";", Desc.CStr());
173  fprintf(F, " fontsize=24;\n");
174  }
175  fprintf(F, "}\n");
176  fclose(F);
177 }
178 
179 // width=0.3, height=0.3, label=\"\", style=filled, color=black
180 void TGraphKey::DrawGViz(const TStr& OutFNm, const TStr& Desc, const TStr& NodeAttrs, const int& Size) const {
181  const TStr DotFNm = OutFNm.GetFMid()+".dot";
182  SaveGViz(DotFNm, Desc, NodeAttrs, Size);
183  TSnap::TSnapDetail::GVizDoLayout(DotFNm, OutFNm, gvlDot);
184 }
185 
186 bool TGraphKey::IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TIntV& NodeIdMap) {
187  const TIntPrV& EdgeV1 = Key1.EdgeV;
188  const TIntPrV& EdgeV2 = Key2.EdgeV;
189  if (Key1.Nodes != Key2.Nodes || EdgeV1.Len() != EdgeV2.Len()) { return false; }
190  for (int e1 = 0; e1 < EdgeV1.Len(); e1++) {
191  const TIntPr Edge2(NodeIdMap[EdgeV1[e1].Val1], NodeIdMap[EdgeV1[e1].Val2]);
192  if (EdgeV2.SearchBin(Edge2) == -1) return false;
193  }
194  return true;
195 }
196 
197 bool TGraphKey::IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TVec<TIntV>& NodeIdMapV) {
198  int IsoPermId;
199  return IsIsomorph(Key1, Key2, NodeIdMapV, IsoPermId);
200 }
201 
202 bool TGraphKey::IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TVec<TIntV>& NodeIdMapV, int& IsoPermId) {
203  const TIntPrV& EdgeV1 = Key1.EdgeV;
204  const TIntPrV& EdgeV2 = Key2.EdgeV;
205  //for (int i = 0; i < EdgeV1.Len(); i++) printf("\t%d - %d\n", EdgeV1[i].Val1, EdgeV1[i].Val2); printf("\n");
206  //for (int i = 0; i < EdgeV2.Len(); i++) printf("\t%d - %d\n", EdgeV2[i].Val1, EdgeV2[i].Val2);
207  if (Key1.Nodes != Key2.Nodes || EdgeV1.Len() != EdgeV2.Len()) return false;
208  const int Nodes = NodeIdMapV[0].Len();
209  // fast adjecency matrix
210  TIntV AdjMtx2(Nodes*Nodes);
211  for (int i = 0; i < EdgeV2.Len(); i++) {
212  AdjMtx2[EdgeV2[i].Val1*Nodes + EdgeV2[i].Val2] = 1;
213  }
214  for (int perm = 0; perm < NodeIdMapV.Len(); perm++) {
215  const TIntV& NodeIdMap = NodeIdMapV[perm];
216  bool IsIso = true;
217  for (int e1 = 0; e1 < EdgeV1.Len(); e1++) {
218  const int NId1 = NodeIdMap[EdgeV1[e1].Val1];
219  const int NId2 = NodeIdMap[EdgeV1[e1].Val2];
220  if (AdjMtx2[NId1*Nodes + NId2] != 1) {
221  IsIso = false; break; }
222  }
223  if (IsIso) {
224  IsoPermId = perm;
225  return true; }
226  }
227  IsoPermId = -1;
228  return false;
229 }
230 
232 // Simple Edge Graph
233 bool TSimpleGraph::Join(const TSimpleGraph& G1, const TSimpleGraph& G2) {
234  const int Edges1 = G1.GetEdges();
235  const int Edges2 = G2.GetEdges();
236  const TIntPrV& EdgeV1 = G1.EdgeV;
237  const TIntPrV& EdgeV2 = G2.EdgeV;
238  const int MxEdges = Edges1+1;
239  if (GetEdges() != MxEdges) EdgeV.Gen(MxEdges);
240  IAssert(Edges1 == Edges2);
241 
242  int e=0, g1=0, g2=0;
243  while (g1 < Edges1 && g2 < Edges2) {
244  if (e == MxEdges) return false;
245  if (abs(g1 - g2) > 1) return false;
246  if (EdgeV1[g1] == EdgeV2[g2]) { e++; g1++; g2++; }
247  else if (EdgeV1[g1] < EdgeV2[g2]) { e++; g1++; }
248  else { e++; g2++; }
249  }
250 
251  e=0; g1=0; g2=0;
252  while (g1 < Edges1 && g2 < Edges2) {
253  if (EdgeV1[g1] == EdgeV2[g2]) {
254  EdgeV[e] = EdgeV1[g1]; e++; g1++; g2++; }
255  else if (EdgeV1[g1] < EdgeV2[g2]) {
256  EdgeV[e] = EdgeV1[g1]; e++; g1++; }
257  else {
258  EdgeV[e] = EdgeV2[g2]; e++; g2++; }
259  }
260  if (g1 == Edges1 && g2 == Edges2 && e == MxEdges) return true;
261  if (e+1 == MxEdges) {
262  if (g1+1 == Edges1 && g2 == Edges2) {
263  EdgeV[e] = EdgeV1.Last();
264  return true;
265  }
266  if (g1 == Edges1 && g2+1 == Edges2) {
267  EdgeV[e] = EdgeV2.Last();
268  return true;
269  }
270  }
271  return false;
272 }
273 
274 void TSimpleGraph::Dump(const TStr& Desc) const {
275  if (! Desc.Empty()) printf("%s. Edges: %d\n", Desc.CStr(), EdgeV.Len());
276  else printf("Edges: %d\n", EdgeV.Len());
277  for (int i = 0; i < EdgeV.Len(); i++) {
278  printf("\t%d\t%d\n", EdgeV[i].Val1(), EdgeV[i].Val2());
279  }
280 }
281 
283  // singe edge sub-graphs
284  SgV.Gen(NGraph->GetEdges(), 0);
285  TSimpleGraph SimpleG;
286  TIntPrV& EdgeV = SimpleG.GetEdgeV();
287  EdgeV.Gen(1);
288  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
289  for (int e = 0; e < NI.GetOutDeg(); e++) {
290  EdgeV[0] = TIntPr(NI.GetId(), NI.GetOutNId(e));
291  SgV.Add(SimpleG);
292  }
293  }
294  SgV.Sort();
295  // two edge sub-graphs
296  EdgeV.Gen(2);
297  for (int g1 = 0; g1 < SgV.Len()-1; g1++) {
298  const TIntPr& E1 = SgV[g1].GetEdgeV()[0];
299  for (int g2 = g1+1; g2 < SgV.Len(); g2++) {
300  const TIntPr& E2 = SgV[g2].GetEdgeV()[0];
301  if (E1.Val2 == E2.Val1 || E1.Val1 == E2.Val2 || E1.Val1 == E2.Val1 || E1.Val2 == E2.Val2) {
302  EdgeV[0] = TMath::Mn(E1, E2);
303  EdgeV[1] = TMath::Mx(E1, E2);
304  SimpleG.Dump();
305  NextSgV.Add(SimpleG);
306  }
307  }
308  }
310 }
311 
312 void TSubGraphsEnum::EnumSubGraphs(const int& MaxEdges) {
313  TExeTm ExeTm;
314  Gen2Graphs();
315  printf(" %2d edge graphs: %d\t[%s]\n", 2, SgV.Len(), ExeTm.GetTmStr()); ExeTm.Tick();
316  //for (int i = 0; i < SgV.Len(); i++) { SgV[i].Dump(TStr::Fmt(" %d", i+1)); }
317  //printf("**************************************************************\n");
318  TSimpleGraph SimpleG;
319  TIntPrV& EdgeV = SimpleG.GetEdgeV();
320  // multiple edge sub-graphs
321  for (int edges = 3; edges <= MaxEdges; edges++) {
322  EdgeV.Clr();
323  printf(" %2d edge graphs:", edges);
324  for (int g1 = 0; g1 < SgV.Len()-1; g1++) {
325  for (int g2 = g1+1; g2 < SgV.Len(); g2++) {
326  if (SimpleG.Join(SgV[g1], SgV[g2])) { NextSgV.Add(SimpleG); }
327  }
328  }
329  printf(" candidates: %8d [%s]", NextSgV.Len(), ExeTm.GetTmStr()); ExeTm.Tick();
330  NextSgV.Sort();
331  SgV.Gen(NextSgV.Len(), 0);
332  SgV.Add(NextSgV[0]);
333  for (int i = 1; i < NextSgV.Len(); i++) {
334  if (SgV.Last() != NextSgV[i]) {
335  SgV.Add(NextSgV[i]);
336  }
337  }
338  NextSgV.Clr(false);
339  printf(" total: %8d [%s]\n", SgV.Len(), ExeTm.GetTmStr()); ExeTm.Tick();
340  //for (int i = 0; i < SgV.Len(); i++) { SgV[i].Dump(TStr::Fmt(" %d", i+1)); }
341  //printf("**************************************************************\n");
342  }
343 }
344 
345 void TSubGraphsEnum::RecurBfs(const int& MxDepth) {
346  TExeTm ExeTm;
347  SgV.Clr(true);
348  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
349  TSimpleGraph SimpleG;
350  RecurBfs(NI.GetId(), MxDepth, SimpleG);
351  //NGraph->DelNode(NI.GetId());
352  printf(".");
353  }
354  printf("\ncandidates: %d\n", SgV.Len());
355  SgV.Sort();
356  int Cnt = 1;
357  for (int i = 1; i < SgV.Len(); i++) {
358  if (SgV[i-1] != SgV[i]) Cnt++;
359  }
360  printf("distinct: %d\t[%s]\n", Cnt, ExeTm.GetTmStr());
361 }
362 
363 void TSubGraphsEnum::RecurBfs(const int& NId, const int& Depth, TSimpleGraph& PrevG) {
364  if (Depth == 0) {
365  TIntPrV& EdgeV = PrevG();
366  EdgeV.Sort();
367  for (int i = 1; i < EdgeV.Len(); i++) {
368  if (EdgeV[i-1] == EdgeV[i]) { return; }
369  }
370  SgV.Add(PrevG);
371  return;
372  }
373  const TNGraph::TNodeI NI = NGraph ->GetNI(NId);
374  for (int e = 0; e < NI.GetOutDeg(); e++) {
375  TSimpleGraph CurG = PrevG;
376  CurG.AddEdge(NI.GetId(), NI.GetOutNId(e));
377  RecurBfs(NI.GetOutNId(e), Depth-1, CurG);
378  }
379  for (int e = 0; e < NI.GetInDeg(); e++) {
380  TSimpleGraph CurG = PrevG;
381  CurG.AddEdge(NI.GetInNId(e), NI.GetId());
382  RecurBfs(NI.GetInNId(e), Depth-1, CurG);
383  }
384 }
385 
386 void TSubGraphsEnum::RecurBfs1(const int& MxDepth) {
387  TExeTm ExeTm;
388  SgV.Clr(true);
389  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
390  TSimpleGraph SimpleG;
391  RecurBfs1(NI.GetId(), MxDepth);
392  //NGraph->DelNode(NI.GetId());
393  printf(".");
394  }
395  printf("candidates: %d\n", SgV.Len());
396  SgV.Sort();
397  int Cnt = 1;
398  for (int i = 1; i < SgV.Len(); i++) {
399  if (SgV[i-1]!=SgV[i]) {
400  //SgV[i].Dump();
401  Cnt++;
402  }
403  }
404  printf("distinct: %d\t[%s]\n", Cnt, ExeTm.GetTmStr());
405 }
406 
407 void TSubGraphsEnum::RecurBfs1(const int& NId, const int& Depth) {
408  if (Depth == 0) {
409  TIntPrV EdgeV;
410  EdgeH.GetKeyV(EdgeV);
411  EdgeV.Sort();
412  SgV.Add(EdgeV);
413  return;
414  }
415  const TNGraph::TNodeI NI = NGraph ->GetNI(NId);
416  for (int e = 0; e < NI.GetOutDeg(); e++) {
417  const TIntPr Edge(NId, NI.GetOutNId(e));
418  if (! EdgeH.IsKey(Edge)) {
419  EdgeH.AddKey(Edge);
420  RecurBfs1(NI.GetOutNId(e), Depth-1);
421  EdgeH.DelKey(Edge);
422  }
423  }
424  for (int e = 0; e < NI.GetInDeg(); e++) {
425  const TIntPr Edge(NI.GetInNId(e), NId);
426  if (! EdgeH.IsKey(Edge)) {
427  EdgeH.AddKey(Edge);
428  RecurBfs1(NI.GetInNId(e), Depth-1);
429  EdgeH.DelKey(Edge);
430  }
431  }
432 }
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
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
TStr GetFMid() const
Definition: dt.cpp:1403
Definition: tm.h:355
TSimpleGraphV NextSgV
Definition: ghash.h:562
Simple directed/undirected graph defined by its edges.
Definition: ghash.h:539
TFltV SigV
Definition: ghash.h:14
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
void Save(TSOut &SOut) const
Definition: dt.h:1153
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TInt Nodes
Definition: ghash.h:12
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TIntPrV & GetEdgeV()
Definition: ghash.h:551
TSimpleGraphV SgV
Definition: ghash.h:562
int GetEdges() const
Definition: ghash.h:548
bool Join(const TSimpleGraph &G1, const TSimpleGraph &G2)
Definition: ghash.cpp:233
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 EnumSubGraphs(const int &MaxEdges)
Definition: ghash.cpp:312
Definition: dt.h:1386
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
void AddEdge(const int &SrcNId, const int &DstNId)
Definition: ghash.h:549
const char * GetTmStr() const
Definition: tm.h:370
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
TGraphKey & operator=(const TGraphKey &GraphKey)
Definition: ghash.cpp:37
static void Svd(const TFltVV &InMtx, TFltVV &LSingV, TFltV &SingValV, TFltVV &RSingV)
Definition: xmath.cpp:1232
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
void RecurBfs(const int &MxDepth)
Definition: ghash.cpp:345
static const int RoundTo
Definition: ghash.h:9
static double Round(const double &Val)
Definition: xmath.h:16
TIntPrV EdgeV
Definition: ghash.h:541
int AddKey(const TKey &Key)
Definition: shash.h:1254
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void Dump(const TStr &Desc=TStr()) const
Definition: ghash.cpp:274
TGraphKey()
Definition: ghash.h:17
void Save(TSOut &SOut) const
Definition: ghash.cpp:32
Definition: gviz.h:3
TIntPrV EdgeV
Definition: ghash.h:13
void Tick()
Definition: tm.h:364
void TakeGraph(const PNGraph &Graph)
Creates a key from a given directed graph.
Definition: ghash.cpp:58
Definition: fl.h:128
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:382
int GetNodes() const
Returns the number of nodes in the graph.
Definition: ghash.h:31
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
PNGraph GetNGraph() const
Returns the directed graph stored in the GraphKey object.
Definition: ghash.cpp:47
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
int AddKey(const TKey &Key)
Definition: hash.h:373
TInt VariantId
Definition: ghash.h:15
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
int GetId() const
Returns ID of the current node.
Definition: graph.h:400
Small Directed Graphs.
Definition: ghash.h:7
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
Definition: dt.h:412
bool Empty() const
Definition: dt.h:491
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
void Gen2Graphs()
Definition: ghash.cpp:282
void RecurBfs1(const int &MxDepth)
Definition: ghash.cpp:386
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
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
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1073
void SaveTxt(FILE *F) const
Saves the graph as a list of edges.
Definition: ghash.cpp:147
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
char * CStr()
Definition: dt.h:479
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
PNGraph NGraph
Definition: ghash.h:564
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
const TVal & At(const TSizeTy &X, const TSizeTy &Y) const
Definition: ds.h:2256