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