SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
ggen.cpp
Go to the documentation of this file.
1 // Graph Generators
3 namespace TSnap {
4 
5 PBPGraph GenRndBipart(const int& LeftNodes, const int& RightNodes, const int& Edges, TRnd& Rnd) {
6  PBPGraph G = TBPGraph::New();
7  for (int i = 0; i < LeftNodes; i++) { G->AddNode(i, true); }
8  for (int i = 0; i < RightNodes; i++) { G->AddNode(LeftNodes+i, false); }
9  IAssertR(Edges <= LeftNodes*RightNodes, "Too many edges in the bipartite graph!");
10  for (int edges = 0; edges < Edges; ) {
11  const int LNId = Rnd.GetUniDevInt(LeftNodes);
12  const int RNId = LeftNodes + Rnd.GetUniDevInt(RightNodes);
13  if (G->AddEdge(LNId, RNId) != -2) { edges++; } // is new edge
14  }
15  return G;
16 }
17 
18 PUNGraph GenRndDegK(const int& Nodes, const int& NodeDeg, const int& NSwitch, TRnd& Rnd) {
19  // create degree sequence
20  TIntV DegV(Nodes, 0);
21  int DegSum=0;
22  for (int i = 0; i < Nodes; i++) {
23  DegV.Add(NodeDeg);
24  DegSum += NodeDeg;
25  }
26  IAssert(DegSum % 2 == 0);
27  PUNGraph G = GenDegSeq(DegV, Rnd); // get some graph that obeys the degree sequnce
28  return GenRewire(G, NSwitch, Rnd); // make it random
29 }
30 
34 PUNGraph GenRndPowerLaw(const int& Nodes, const double& PowerExp, const bool& ConfModel, TRnd& Rnd) {
35  TIntV DegSeqV;
36  uint DegSum=0;
37  for (int n = 0; n < Nodes; n++) {
38  const int Val = (int) TMath::Round(Rnd.GetPowerDev(PowerExp));
39  if (! (Val >= 1 && Val < Nodes/2)) { n--; continue; } // skip nodes with too large degree
40  DegSeqV.Add(Val);
41  DegSum += Val;
42  }
43  printf("%d nodes, %u edges\n", Nodes, DegSum);
44  if (DegSum % 2 == 1) { DegSeqV[0] += 1; }
45  if (ConfModel) {
46  // use configuration model -- fast but does not exactly obey the degree sequence
47  return GenConfModel(DegSeqV, Rnd);
48  } else {
49  DegSeqV.Sort();
50  DegSeqV.Reverse();
51  PUNGraph G = TSnap::GenDegSeq(DegSeqV, Rnd);
52  return TSnap::GenRewire(G, 10, Rnd);
53  }
54 }
55 
61 PUNGraph GenDegSeq(const TIntV& DegSeqV, TRnd& Rnd) {
62  const int Nodes = DegSeqV.Len();
63  PUNGraph GraphPt = TUNGraph::New();
64  TUNGraph& Graph = *GraphPt;
65  Graph.Reserve(Nodes, -1);
66  TIntH DegH(DegSeqV.Len(), true);
67 
68  IAssertR(DegSeqV.IsSorted(false), "DegSeqV must be sorted in descending order.");
69  int DegSum=0, edge=0;
70  for (int node = 0; node < Nodes; node++) {
71  IAssert(Graph.AddNode(node) == node);
72  DegH.AddDat(node, DegSeqV[node]);
73  DegSum += DegSeqV[node];
74  }
75  IAssert(DegSum % 2 == 0);
76  while (! DegH.Empty()) {
77  // pick random nodes and connect
78  const int NId1 = DegH.GetKey(DegH.GetRndKeyId(Rnd, 0.5));
79  const int NId2 = DegH.GetKey(DegH.GetRndKeyId(Rnd, 0.5));
80  IAssert(DegH.IsKey(NId1) && DegH.IsKey(NId2));
81  if (NId1 == NId2) {
82  if (DegH.GetDat(NId1) == 1) { continue; }
83  // find rnd edge, break it, and connect the endpoints to the nodes
84  const TIntPr Edge = TSnapDetail::GetRndEdgeNonAdjNode(GraphPt, NId1, -1);
85  if (Edge.Val1==-1) { continue; }
86  Graph.DelEdge(Edge.Val1, Edge.Val2);
87  Graph.AddEdge(Edge.Val1, NId1);
88  Graph.AddEdge(NId1, Edge.Val2);
89  if (DegH.GetDat(NId1) == 2) { DegH.DelKey(NId1); }
90  else { DegH.GetDat(NId1) -= 2; }
91  } else {
92  if (! Graph.IsEdge(NId1, NId2)) {
93  Graph.AddEdge(NId1, NId2); } // good edge
94  else {
95  // find rnd edge, break and cross-connect
96  const TIntPr Edge = TSnapDetail::GetRndEdgeNonAdjNode(GraphPt, NId1, NId2);
97  if (Edge.Val1==-1) { continue; }
98  Graph.DelEdge(Edge.Val1, Edge.Val2);
99  Graph.AddEdge(NId1, Edge.Val1);
100  Graph.AddEdge(NId2, Edge.Val2);
101  }
102  if (DegH.GetDat(NId1)==1) { DegH.DelKey(NId1); }
103  else { DegH.GetDat(NId1) -= 1; }
104  if (DegH.GetDat(NId2)==1) { DegH.DelKey(NId2); }
105  else { DegH.GetDat(NId2) -= 1; }
106  }
107  if (++edge % 1000 == 0) {
108  printf("\r %dk / %dk", edge/1000, DegSum/2000); }
109  }
110  return GraphPt;
111 }
112 
113 
122 PUNGraph GenConfModel(const TIntV& DegSeqV, TRnd& Rnd) {
123  const int Nodes = DegSeqV.Len();
124  PUNGraph GraphPt = TUNGraph::New();
125  TUNGraph& Graph = *GraphPt;
126  Graph.Reserve(Nodes, -1);
127  TIntV NIdDegV(DegSeqV.Len(), 0);
128  int DegSum=0, edges=0;
129  for (int node = 0; node < Nodes; node++) {
130  Graph.AddNode(node);
131  for (int d = 0; d < DegSeqV[node]; d++) { NIdDegV.Add(node); }
132  DegSum += DegSeqV[node];
133  }
134  NIdDegV.Shuffle(Rnd);
135  TIntPrSet EdgeH(DegSum/2); // set of all edges, is faster than graph edge lookup
136  if (DegSum % 2 != 0) {
137  printf("Seg seq is odd [%d]: ", DegSeqV.Len());
138  for (int d = 0; d < TMath::Mn(100, DegSeqV.Len()); d++) { printf(" %d", (int)DegSeqV[d]); }
139  printf("\n");
140  }
141  int u=0, v=0;
142  for (int c = 0; NIdDegV.Len() > 1; c++) {
143  u = Rnd.GetUniDevInt(NIdDegV.Len());
144  while ((v = Rnd.GetUniDevInt(NIdDegV.Len())) == u) { }
145  if (u > v) { Swap(u, v); }
146  const int E1 = NIdDegV[u];
147  const int E2 = NIdDegV[v];
148  if (v == NIdDegV.Len()-1) { NIdDegV.DelLast(); }
149  else { NIdDegV[v] = NIdDegV.Last(); NIdDegV.DelLast(); }
150  if (u == NIdDegV.Len()-1) { NIdDegV.DelLast(); }
151  else { NIdDegV[u] = NIdDegV.Last(); NIdDegV.DelLast(); }
152  if (E1 == E2 || EdgeH.IsKey(TIntPr(E1, E2))) { continue; }
153  EdgeH.AddKey(TIntPr(E1, E2));
154  Graph.AddEdge(E1, E2);
155  edges++;
156  if (c % (DegSum/100+1) == 0) { printf("\r configuration model: iter %d: edges: %d, left: %d", c, edges, NIdDegV.Len()/2); }
157  }
158  printf("\n");
159  return GraphPt;
160 }
161 
168 PUNGraph GenRewire(const PUNGraph& OrigGraph, const int& NSwitch, TRnd& Rnd) {
169  const int Nodes = OrigGraph->GetNodes();
170  const int Edges = OrigGraph->GetEdges();
171  PUNGraph GraphPt = TUNGraph::New();
172  TUNGraph& Graph = *GraphPt;
173  Graph.Reserve(Nodes, -1);
174  TExeTm ExeTm;
175  // generate a graph that satisfies the constraints
176  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
177  TIntPrSet EdgeSet(Edges);
178  for (TUNGraph::TNodeI NI = OrigGraph->BegNI(); NI < OrigGraph->EndNI(); NI++) {
179  const int NId = NI.GetId();
180  for (int e = 0; e < NI.GetOutDeg(); e++) {
181  if (NId <= NI.GetOutNId(e)) { continue; }
182  EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e)));
183  }
184  Graph.AddNode(NI.GetId());
185  }
186  // edge switching
187  uint skip=0;
188  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
189  const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
190  const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
191  if (keyId1 == keyId2) { skip++; continue; }
192  const TIntPr& E1 = EdgeSet[keyId1];
193  const TIntPr& E2 = EdgeSet[keyId2];
194  TIntPr NewE1(E1.Val1, E2.Val1), NewE2(E1.Val2, E2.Val2);
195  if (NewE1.Val1 > NewE1.Val2) { Swap(NewE1.Val1, NewE1.Val2); }
196  if (NewE2.Val1 > NewE2.Val2) { Swap(NewE2.Val1, NewE2.Val2); }
197  if (NewE1!=NewE2 && NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
198  EdgeSet.DelKeyId(keyId1); EdgeSet.DelKeyId(keyId2);
199  EdgeSet.AddKey(TIntPr(NewE1));
200  EdgeSet.AddKey(TIntPr(NewE2));
201  } else { skip++; }
202  if (swps % Edges == 0) {
203  printf("\r %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
204  if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
205  }
206  }
207  printf("\r total %uk switchings attempted, %uk skiped [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
208  for (int e = 0; e < EdgeSet.Len(); e++) {
209  Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
210  return GraphPt;
211 }
212 
219 PNGraph GenRewire(const PNGraph& OrigGraph, const int& NSwitch, TRnd& Rnd) {
220  const int Nodes = OrigGraph->GetNodes();
221  const int Edges = OrigGraph->GetEdges();
222  PNGraph GraphPt = TNGraph::New();
223  TNGraph& Graph = *GraphPt;
224  Graph.Reserve(Nodes, -1);
225  TExeTm ExeTm;
226  // generate a graph that satisfies the constraints
227  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
228  TIntPrSet EdgeSet(Edges);
229  for (TNGraph::TNodeI NI = OrigGraph->BegNI(); NI < OrigGraph->EndNI(); NI++) {
230  const int NId = NI.GetId();
231  for (int e = 0; e < NI.GetOutDeg(); e++) {
232  EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e))); }
233  Graph.AddNode(NI);
234  }
235  // edge switching
236  uint skip=0;
237  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
238  const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
239  const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
240  if (keyId1 == keyId2) { skip++; continue; }
241  const TIntPr& E1 = EdgeSet[keyId1];
242  const TIntPr& E2 = EdgeSet[keyId2];
243  TIntPr NewE1(E1.Val1, E2.Val2), NewE2(E2.Val1, E1.Val2);
244  if (NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && NewE1.Val1!=NewE2.Val1 && NewE1.Val2!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
245  EdgeSet.DelKeyId(keyId1); EdgeSet.DelKeyId(keyId2);
246  EdgeSet.AddKey(TIntPr(NewE1));
247  EdgeSet.AddKey(TIntPr(NewE2));
248  } else { skip++; }
249  if (swps % Edges == 0) {
250  printf("\r %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
251  if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
252  }
253  }
254  printf("\r total %uk switchings attempted, %uk skiped [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
255  for (int e = 0; e < EdgeSet.Len(); e++) {
256  Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
257  return GraphPt;
258 }
259 
266 PBPGraph GenRewire(const PBPGraph& OrigGraph, const int& NSwitch, TRnd& Rnd) {
267  const int Nodes = OrigGraph->GetNodes();
268  const int Edges = OrigGraph->GetEdges();
269  PBPGraph GraphPt = TBPGraph::New();
270  TBPGraph& Graph = *GraphPt;
271  Graph.Reserve(Nodes, -1);
272  TExeTm ExeTm;
273  // generate a graph that satisfies the constraints
274  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
275  TIntPrSet EdgeSet(Edges);
276  for (TBPGraph::TNodeI NI = OrigGraph->BegLNI(); NI < OrigGraph->EndLNI(); NI++) {
277  const int NId = NI.GetId();
278  for (int e = 0; e < NI.GetOutDeg(); e++) {
279  EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e))); } // edges left-->right
280  Graph.AddNode(NI.GetId(), true); } // left nodes
281  for (TBPGraph::TNodeI NI = OrigGraph->BegRNI(); NI < OrigGraph->EndRNI(); NI++) {
282  Graph.AddNode(NI.GetId(), false); } // right nodes
283  IAssert(EdgeSet.Len() == Edges);
284  // edge switching
285  uint skip=0;
286  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
287  const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
288  const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
289  if (keyId1 == keyId2) { skip++; continue; }
290  const TIntPr& E1 = EdgeSet[keyId1];
291  const TIntPr& E2 = EdgeSet[keyId2];
292  TIntPr NewE1(E1.Val1, E2.Val2), NewE2(E2.Val1, E1.Val2);
293  if (NewE1!=NewE2 && NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
294  EdgeSet.DelKeyId(keyId1); EdgeSet.DelKeyId(keyId2);
295  EdgeSet.AddKey(TIntPr(NewE1));
296  EdgeSet.AddKey(TIntPr(NewE2));
297  } else { skip++; }
298  if (swps % Edges == 0) {
299  printf("\r %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
300  if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
301  }
302  }
303  printf("\r total %uk switchings attempted, %uk skiped [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
304  for (int e = 0; e < EdgeSet.Len(); e++) {
305  Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
306  return GraphPt;
307 }
308 
313 PUNGraph GenPrefAttach(const int& Nodes, const int& NodeOutDeg, TRnd& Rnd) {
314  PUNGraph GraphPt = PUNGraph::New();
315  TUNGraph& Graph = *GraphPt;
316  Graph.Reserve(Nodes, NodeOutDeg*Nodes);
317  TIntV NIdV(NodeOutDeg*Nodes, 0);
318  // first edge
319  Graph.AddNode(0); Graph.AddNode(1);
320  NIdV.Add(0); NIdV.Add(1);
321  Graph.AddEdge(0, 1);
322  TIntSet NodeSet;
323  for (int node = 2; node < Nodes; node++) {
324  NodeSet.Clr(false);
325  while (NodeSet.Len() < NodeOutDeg && NodeSet.Len() < node) {
326  NodeSet.AddKey(NIdV[Rnd.GetUniDevInt(NIdV.Len())]);
327  }
328  const int N = Graph.AddNode();
329  for (int i = 0; i < NodeSet.Len(); i++) {
330  Graph.AddEdge(N, NodeSet[i]);
331  NIdV.Add(N);
332  NIdV.Add(NodeSet[i]);
333  }
334  }
335  return GraphPt;
336 }
337 
338 PUNGraph GenConfModel(const PUNGraph& G) {
339  TIntV DegSeqV(G->GetNodes(), 0);
340  TSnap::GetDegSeqV(G, DegSeqV);
341  return TSnap::GenConfModel(DegSeqV);
342 }
343 
344 namespace TSnapDetail {
346 void GetSphereDev(const int& Dim, TRnd& Rnd, TFltV& ValV) {
347  if (ValV.Len() != Dim) { ValV.Gen(Dim); }
348  double Length = 0.0;
349  for (int i = 0; i < Dim; i++) {
350  ValV[i] = Rnd.GetNrmDev();
351  Length += TMath::Sqr(ValV[i]); }
352  Length = 1.0 / sqrt(Length);
353  for (int i = 0; i < Dim; i++) {
354  ValV[i] *= Length;
355  }
356 }
357 } // namespace TSnapDetail
358 
364 PUNGraph GenGeoPrefAttach(const int& Nodes, const int& OutDeg, const double& Beta, TRnd& Rnd) {
365  PUNGraph G = TUNGraph::New(Nodes, Nodes*OutDeg);
366  TFltTrV PointV(Nodes, 0);
367  TFltV ValV;
368  // points on a sphere of radius 1/(2*pi)
369  const double Rad = 0.5 * TMath::Pi;
370  for (int i = 0; i < Nodes; i++) {
371  TSnapDetail::GetSphereDev(3, Rnd, ValV);
372  PointV.Add(TFltTr(Rad*ValV[0], Rad*ValV[1], Rad*ValV[2]));
373  }
374  const double R2 = TMath::Sqr(log((double) Nodes) / (pow((double) Nodes, 0.5-Beta)));
375  TIntV DegV, NIdV;
376  int SumDeg;
377  for (int t = 0; t < Nodes; t++) {
378  const int pid = t;
379  const TFltTr& P1 = PointV[pid];
380  // add node
381  if (! G->IsNode(pid)) { G->AddNode(pid); }
382  // find neighborhood
383  DegV.Clr(false); NIdV.Clr(false); SumDeg=0;
384  for (int p = 0; p < t; p++) {
385  const TFltTr& P2 = PointV[p];
386  if (TMath::Sqr(P1.Val1-P2.Val1)+TMath::Sqr(P1.Val2-P2.Val2)+TMath::Sqr(P1.Val3-P2.Val3) < R2) {
387  NIdV.Add(p);
388  DegV.Add(G->GetNI(p).GetDeg()+1);
389  SumDeg += DegV.Last();
390  }
391  }
392  // add edges
393  for (int m = 0; m < OutDeg; m++) {
394  const int rnd = Rnd.GetUniDevInt(SumDeg);
395  int sum = 0, dst = -1;
396  for (int s = 0; s < DegV.Len(); s++) {
397  sum += DegV[s];
398  if (rnd < sum) { dst=s; break; }
399  }
400  if (dst != -1) {
401  G->AddEdge(pid, NIdV[dst]);
402  SumDeg -= DegV[dst];
403  NIdV.Del(dst); DegV.Del(dst);
404  }
405  }
406  }
407  return G;
408 }
409 
415 PUNGraph GenSmallWorld(const int& Nodes, const int& NodeOutDeg, const double& RewireProb, TRnd& Rnd) {
416  THashSet<TIntPr> EdgeSet(Nodes*NodeOutDeg);
417 
418  IAssertR(Nodes > NodeOutDeg, TStr::Fmt("Insufficient nodes for out degree, %d!", NodeOutDeg));
419  for (int node = 0; node < Nodes; node++) {
420  const int src = node;
421  for (int edge = 1; edge <= NodeOutDeg; edge++) {
422  int dst = (node+edge) % Nodes; // edge to next neighbor
423  if (Rnd.GetUniDev() < RewireProb) { // random edge
424  dst = Rnd.GetUniDevInt(Nodes);
425  while (dst == src || EdgeSet.IsKey(TIntPr(src, dst))) {
426  dst = Rnd.GetUniDevInt(Nodes); }
427  }
428  EdgeSet.AddKey(TIntPr(src, dst));
429  }
430  }
431  PUNGraph GraphPt = TUNGraph::New();
432  TUNGraph& Graph = *GraphPt;
433  Graph.Reserve(Nodes, EdgeSet.Len());
434  int node;
435  for (node = 0; node < Nodes; node++) {
436  IAssert(Graph.AddNode(node) == node);
437  }
438  for (int edge = 0; edge < EdgeSet.Len(); edge++) {
439  Graph.AddEdge(EdgeSet[edge].Val1, EdgeSet[edge].Val2);
440  }
441  Graph.Defrag();
442  return GraphPt;
443 }
444 
445 PNGraph GenForestFire(const int& Nodes, const double& FwdProb, const double& BckProb) {
446  return TForestFire::GenGraph(Nodes, FwdProb, BckProb);
447 }
448 
456 PNGraph GenCopyModel(const int& Nodes, const double& Beta, TRnd& Rnd) {
457  PNGraph GraphPt = TNGraph::New();
458  TNGraph& Graph = *GraphPt;
459  Graph.Reserve(Nodes, Nodes);
460  const int startNId = Graph.AddNode();
461  Graph.AddEdge(startNId, startNId);
462  for (int n = 1; n < Nodes; n++) {
463  const int rnd = Graph.GetRndNId();
464  const int NId = Graph.AddNode();
465  if (Rnd.GetUniDev() < Beta) {
466  Graph.AddEdge(NId, rnd); }
467  else {
468  const TNGraph::TNodeI NI = Graph.GetNI(rnd);
469  const int rnd2 = Rnd.GetUniDevInt(NI.GetOutDeg());
470  Graph.AddEdge(NId, NI.GetOutNId(rnd2));
471  }
472  }
473  return GraphPt;
474 }
475 
481 PNGraph GenRMat(const int& Nodes, const int& Edges, const double& A, const double& B, const double& C, TRnd& Rnd) {
482  PNGraph GraphPt = TNGraph::New();
483  TNGraph& Graph = *GraphPt;
484  Graph.Reserve(Nodes, Edges);
485  IAssert(A+B+C < 1.0);
486  int rngX, rngY, offX, offY;
487  int Depth=0, Collisions=0, Cnt=0, PctDone=0;
488  const int EdgeGap = Edges / 100 + 1;
489  // sum of parameters (probabilities)
490  TVec<double> sumA(128, 0), sumAB(128, 0), sumAC(128, 0), sumABC(128, 0); // up to 2^128 vertices ~ 3.4e38
491  for (int i = 0; i < 128; i++) {
492  const double a = A * (Rnd.GetUniDev() + 0.5);
493  const double b = B * (Rnd.GetUniDev() + 0.5);
494  const double c = C * (Rnd.GetUniDev() + 0.5);
495  const double d = (1.0 - (A+B+C)) * (Rnd.GetUniDev() + 0.5);
496  const double abcd = a+b+c+d;
497  sumA.Add(a / abcd);
498  sumAB.Add((a+b) / abcd);
499  sumAC.Add((a+c) / abcd);
500  sumABC.Add((a+b+c) / abcd);
501  }
502  // nodes
503  for (int node = 0; node < Nodes; node++) {
504  IAssert(Graph.AddNode(-1) == node);
505  }
506  // edges
507  for (int edge = 0; edge < Edges; ) {
508  rngX = Nodes; rngY = Nodes; offX = 0; offY = 0;
509  Depth = 0;
510  // recurse the matrix
511  while (rngX > 1 || rngY > 1) {
512  const double RndProb = Rnd.GetUniDev();
513  if (rngX>1 && rngY>1) {
514  if (RndProb < sumA[Depth]) { rngX/=2; rngY/=2; }
515  else if (RndProb < sumAB[Depth]) { offX+=rngX/2; rngX-=rngX/2; rngY/=2; }
516  else if (RndProb < sumABC[Depth]) { offY+=rngY/2; rngX/=2; rngY-=rngY/2; }
517  else { offX+=rngX/2; offY+=rngY/2; rngX-=rngX/2; rngY-=rngY/2; }
518  } else
519  if (rngX>1) { // row vector
520  if (RndProb < sumAC[Depth]) { rngX/=2; rngY/=2; }
521  else { offX+=rngX/2; rngX-=rngX/2; rngY/=2; }
522  } else
523  if (rngY>1) { // column vector
524  if (RndProb < sumAB[Depth]) { rngX/=2; rngY/=2; }
525  else { offY+=rngY/2; rngX/=2; rngY-=rngY/2; }
526  } else { Fail; }
527  Depth++;
528  }
529  // add edge
530  const int NId1 = offX;
531  const int NId2 = offY;
532  if (NId1 != NId2 && ! Graph.IsEdge(NId1, NId2)) {
533  Graph.AddEdge(NId1, NId2);
534  if (++Cnt > EdgeGap) {
535  Cnt=0; printf("\r %d%% edges", ++PctDone); }
536  edge++;
537  } else {
538  Collisions++; }
539  }
540  printf("\r RMat: nodes:%d, edges:%d, Iterations:%d, Collisions:%d (%.1f%%).\n", Nodes, Edges,
541  Edges+Collisions, Collisions, 100*Collisions/double(Edges+Collisions));
542  Graph.Defrag();
543  return GraphPt;
544 }
545 
550 PNGraph GenRMatEpinions() {
551  return GenRMat(75888, 508837, 0.550, 0.228, 0.212);
552 }
553 
554 } // namespace TSnap
THashSet::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TMath::Mn
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSnap
Main namespace for all the Snap global entities.
Definition: alg.h:1
TBPGraph::Reserve
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a biparite graph of Nodes nodes and Edges edges.
Definition: graph.cpp:790
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSnap::GenRMatEpinions
PNGraph GenRMatEpinions()
Generates a R-Mat graph, with a synthetic copy of the Epinions social network.
Definition: ggen.cpp:550
TExeTm
Definition: tm.h:355
THashSet::DelKeyId
void DelKeyId(const int &KeyId)
Definition: shash.h:1134
TRnd
Definition: dt.h:11
TTriple
Definition: ds.h:130
TVec::Del
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSnap::GenRewire
PUNGraph GenRewire(const PUNGraph &OrigGraph, const int &NSwitch, TRnd &Rnd)
Rewire a random undirected graph. Keeps node degrees the same, but randomly rewires the edges...
Definition: ggen.cpp:168
TSnap::GenRMat
PNGraph GenRMat(const int &Nodes, const int &Edges, const double &A, const double &B, const double &C, TRnd &Rnd)
Generates a R-MAT graph using recursive descent into a 2x2 matrix [A,B; C, 1-(A+B+C)].
Definition: ggen.cpp:481
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
uint
unsigned int uint
Definition: bd.h:11
Fail
#define Fail
Definition: bd.h:238
TPt::New
static TPt New()
Definition: bd.h:479
TBPGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:968
TUNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TUNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TBPGraph::AddNode
int AddNode(int NId=-1, const bool &LeftNode=true)
Adds a node of ID NId to the graph.
Definition: graph.cpp:671
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TSnap::GenCopyModel
PNGraph GenCopyModel(const int &Nodes, const double &Beta, TRnd &Rnd)
Generates a random scale-free network using the Copying Model.
Definition: ggen.cpp:456
TTriple::Val1
TVal1 Val1
Definition: ds.h:132
TMath::Sqr
static double Sqr(const double &x)
Definition: xmath.h:12
TSnap::GenRndBipart
PBPGraph GenRndBipart(const int &LeftNodes, const int &RightNodes, const int &Edges, TRnd &Rnd)
Generates a random bipartite graph.
Definition: ggen.cpp:5
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TUNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
TUNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:90
TSnap::TSnapDetail::GetSphereDev
void GetSphereDev(const int &Dim, TRnd &Rnd, TFltV &ValV)
Sample random point from the surface of a Dim-dimensional unit sphere.
Definition: ggen.cpp:346
TTriple::Val2
TVal2 Val2
Definition: ds.h:133
TSnap::GenDegSeq
PUNGraph GenDegSeq(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random graph with exact degree sequence.
Definition: ggen.cpp:61
TSnap::TSnapDetail::GetRndEdgeNonAdjNode
TIntPr GetRndEdgeNonAdjNode(const PGraph &Graph, int NId1, int NId2)
Returns a random edge in a graph Graph where the edge does not touch nodes NId1 and NId2...
Definition: ggen.h:240
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TSnap::GetDegSeqV
void GetDegSeqV(const PGraph &Graph, TIntV &DegV)
Returns a degree sequence vector.
Definition: alg.h:245
TUNGraph
Undirected graph.
Definition: graph.h:32
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
TSnap::GenRndDegK
PUNGraph GenRndDegK(const int &Nodes, const int &NodeDeg, const int &NSwitch, TRnd &Rnd)
Generates a random graph where each node has degree exactly NodeDeg.
Definition: ggen.cpp:18
TNGraph::IsEdge
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
TUNGraph::Reserve
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:302
TNGraph::GetRndNId
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:603
TMath::Round
static double Round(const double &Val)
Definition: xmath.h:16
TUNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
TUNGraph::New
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TSnap::GenForestFire
PNGraph GenForestFire(const int &Nodes, const double &FwdProb, const double &BckProb)
Generates a random Forest Fire, directed graph with given probabilities.
Definition: ggen.cpp:445
TUNGraph::DelEdge
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
TFltTr
TTriple< TFlt, TFlt, TFlt > TFltTr
Definition: ds.h:181
TSnap::GenConfModel
PUNGraph GenConfModel(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random undirect graph with a given degree sequence.
Definition: ggen.cpp:122
TMath::Pi
static double Pi
Definition: xmath.h:8
TSnap::GenPrefAttach
PUNGraph GenPrefAttach(const int &Nodes, const int &NodeOutDeg, TRnd &Rnd)
Generates a power-law degree distribution using Barabasi-Albert model of scale-free graphs...
Definition: ggen.cpp:313
TNGraph::Defrag
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:382
TUNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
THashSet::GetRndKeyId
int GetRndKeyId(TRnd &Rnd) const
Definition: shash.h:1144
TBPGraph::AddEdge
int AddEdge(const int &LeftNId, const int &RightNId)
Adds an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartit...
Definition: graph.cpp:705
TNGraph
Directed graph.
Definition: graph.h:346
TRnd::GetNrmDev
double GetNrmDev()
Definition: dt.cpp:63
THashSet::Len
int Len() const
Definition: shash.h:1121
TPair
Definition: ds.h:32
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
TBPGraph
Bipartite graph.
Definition: graph.h:936
TSnap::GenSmallWorld
PUNGraph GenSmallWorld(const int &Nodes, const int &NodeOutDeg, const double &RewireProb, TRnd &Rnd)
Generates a randomly small-world graph using the Watts-Strogatz model.
Definition: ggen.cpp:415
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TVec::IsSorted
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
THash
Definition: hash.h:97
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TUNGraph::Defrag
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:160
TExeTm::GetSecs
double GetSecs() const
Definition: tm.h:366
TUNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TRnd::GetUniDev
double GetUniDev()
Definition: dt.h:30
TSnap::GenGeoPrefAttach
PUNGraph GenGeoPrefAttach(const int &Nodes, const int &OutDeg, const double &Beta, TRnd &Rnd)
Generates a random scale-free graph using the Geometric Preferential model.
Definition: ggen.cpp:364
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TNGraph::Reserve
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:614
TBPGraph::New
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:1062
TPair::Val2
TVal2 Val2
Definition: ds.h:35
TUNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TPt
Definition: bd.h:196
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1350
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSnap::GenRndPowerLaw
PUNGraph GenRndPowerLaw(const int &Nodes, const double &PowerExp, const bool &ConfModel, TRnd &Rnd)
Generates a random scale-free graph with power-law degree distribution.
Definition: ggen.cpp:34
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TUNGraph::IsEdge
bool IsEdge(const int &SrcNId, const int &DstNId) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: graph.cpp:137
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TForestFire::GenGraph
static PNGraph GenGraph(const int &Nodes, const double &FwdProb, const double &BckProb)
Definition: ff.cpp:250
TUNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
TNGraph::TNodeI::GetOutNId
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
TTriple::Val3
TVal3 Val3
Definition: ds.h:134
TRnd::GetPowerDev
double GetPowerDev(const double &AlphaSlope)
Definition: dt.h:47
Swap
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430