SNAP Library 2.4, Developer Reference  2015-05-11 19:40:56
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.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:463
TStr GetFMid() const
Definition: dt.cpp:1403
Definition: tm.h:354
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:411
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:467
void Save(TSOut &SOut) const
Definition: dt.h:1058
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:278
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TInt Nodes
Definition: ghash.h:12
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:424
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:208
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:1291
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:885
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
void AddEdge(const int &SrcNId, const int &DstNId)
Definition: ghash.h:549
const char * GetTmStr() const
Definition: tm.h:369
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:953
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1218
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graph.cpp:286
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:539
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:363
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:1418
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:332
int GetNodes() const
Returns the number of nodes in the graph.
Definition: ghash.h:31
int GetKeyId(const TKey &Key) const
Definition: hash.h:420
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:327
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:465
int GetId() const
Returns ID of the current node.
Definition: graph.h:344
Small Directed Graphs.
Definition: ghash.h:7
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:350
Definition: dt.h:412
bool Empty() const
Definition: dt.h:488
void Pack()
The vector reduces its capacity (frees memory) to match its size.
Definition: ds.h:987
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:327
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:486
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1002
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:348
char * CStr()
Definition: dt.h:476
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:354
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
const TVal & At(const int &X, const int &Y) const
Definition: ds.h:2142
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:358
PNGraph NGraph
Definition: ghash.h:564
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420