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
ggen.h
Go to the documentation of this file.
1 // TODO ROK, Jure included basic documentation, finalize reference doc
2 
4 // Graph Generators
5 namespace TSnap {
6 
8 // Deterministic graphs
10 template <class PGraph> PGraph GenGrid(const int& Rows, const int& Cols, const bool& IsDir=true);
12 template <class PGraph> PGraph GenStar(const int& Nodes, const bool& IsDir=true);
14 template <class PGraph> PGraph GenCircle(const int& Nodes, const int& NodeOutDeg=1, const bool& IsDir=true);
16 template <class PGraph> PGraph GenFull(const int& Nodes);
18 template <class PGraph> PGraph GenTree(const int& Fanout, const int& Levels, const bool& IsDir=true, const bool& ChildPointsToParent=true);
20 template <class PGraph> PGraph GenBaraHierar(const int& Levels, const bool& IsDir=true);
21 
23 // Random graphs
24 
26 template <class PGraph> PGraph GenRndGnm(const int& Nodes, const int& Edges, const bool& IsDir=true, TRnd& Rnd=TInt::Rnd);
28 PBPGraph GenRndBipart(const int& LeftNodes, const int& RightNodes, const int& Edges, TRnd& Rnd=TInt::Rnd);
30 PUNGraph GenRndDegK(const int& Nodes, const int& NodeDeg, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
32 PUNGraph GenRndPowerLaw(const int& Nodes, const double& PowerExp, const bool& ConfModel=true, TRnd& Rnd=TInt::Rnd);
34 PUNGraph GenDegSeq(const TIntV& DegSeqV, TRnd& Rnd=TInt::Rnd);
36 PUNGraph GenPrefAttach(const int& Nodes, const int& NodeOutDeg, TRnd& Rnd=TInt::Rnd);
38 PUNGraph GenGeoPrefAttach(const int& Nodes, const int& OutDeg, const double& Beta, TRnd& Rnd=TInt::Rnd);
40 PUNGraph GenSmallWorld(const int& Nodes, const int& NodeOutDeg, const double& RewireProb, TRnd& Rnd=TInt::Rnd);
42 PUNGraph GenConfModel(const TIntV& DegSeqV, TRnd& Rnd=TInt::Rnd);
44 PNGraph GenForestFire(const int& Nodes, const double& FwdProb, const double& BckProb);
46 PNGraph GenCopyModel(const int& Nodes, const double& Beta, TRnd& Rnd=TInt::Rnd);
48 PNGraph GenRMat(const int& Nodes, const int& Edges, const double& A, const double& B, const double& C, TRnd& Rnd=TInt::Rnd);
51 
52 
54 PUNGraph GenRewire(const PUNGraph& Graph, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
56 PNGraph GenRewire(const PNGraph& Graph, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
58 PBPGraph GenRewire(const PBPGraph& Graph, const int& NSwitch=100, TRnd& Rnd=TInt::Rnd);
61 
63 // Implementation
64 template <class PGraph>
65 PGraph GenGrid(const int& Rows, const int& Cols, const bool& IsDir) {
66  PGraph GraphPt = PGraph::New();
67  typename PGraph::TObj& Graph = *GraphPt;
68  Graph.Reserve(Rows*Cols, 4*Rows*Cols);
69  int node, r, c;
70  for (node = 0; node < Rows * Cols; node++) {
71  Graph.AddNode(node); }
72  for (r = 0; r < Rows; r++) {
73  for (c = 0; c < Cols; c++) {
74  const int nodeId = Cols*r + c;
75  if (r < Rows-1) { // bottom node
76  Graph.AddEdge(nodeId, nodeId+Cols);
77  if (Graph.HasFlag(gfDirected) && ! IsDir) {
78  Graph.AddEdge(nodeId+Cols, nodeId); }
79  }
80  if (c < Cols-1) { // right node
81  Graph.AddEdge(nodeId, nodeId+1);
82  if (Graph.HasFlag(gfDirected) && ! IsDir) {
83  Graph.AddEdge(nodeId+1, nodeId); }
84  }
85  }
86  }
87  return GraphPt;
88 }
89 
90 template <class PGraph>
91 PGraph GenStar(const int& Nodes, const bool& IsDir) {
92  PGraph Graph = PGraph::TObj::New();
93  Graph->Reserve(Nodes, Nodes);
94  Graph->AddNode(0);
95  for (int n = 1; n < Nodes; n++) {
96  Graph->AddNode(n);
97  Graph->AddEdge(0, n);
98  if (Graph->HasFlag(gfDirected) && ! IsDir) { Graph->AddEdge(n, 0); }
99  }
100  return Graph;
101 }
102 
103 template <class PGraph>
104 PGraph GenCircle(const int& Nodes, const int& NodeOutDeg, const bool& IsDir) {
105  PGraph Graph = PGraph::TObj::New();
106  Graph->Reserve(Nodes, Nodes*NodeOutDeg);
107  for (int n = 0; n < Nodes; n++) {
108  Graph->AddNode(n); }
109  for (int n = 0; n < Nodes; n++) {
110  for (int x = 0; x < NodeOutDeg; x++) {
111  Graph->AddEdge(n, (n+x+1) % Nodes);
112  if (Graph->HasFlag(gfDirected) && ! IsDir) { Graph->AddEdge((n+x+1) % Nodes, n); }
113  }
114  }
115  return Graph;
116 }
117 
118 template <class PGraph>
119 PGraph GenFull(const int& Nodes) {
120  PGraph Graph = PGraph::TObj::New();
121  Graph->Reserve(Nodes, Nodes*Nodes);
122  for (int n = 0; n < Nodes; n++) {
123  Graph->AddNode(n); }
124  for (int n1 = 0; n1 < Nodes; n1++) {
125  for (int n2 = 0; n2 < Nodes; n2++) {
126  if (n1 != n2) { Graph->AddEdge(n1, n2); }
127  }
128  }
129  return Graph;
130 }
131 
132 template <class PGraph>
133 PGraph GenTree(const int& Fanout, const int& Levels, const bool& IsDir, const bool& ChildPointsToParent) {
134  const int Nodes = (int) (pow(double(Fanout), double(Levels+1)) - 1) / (Fanout - 1);
135  const int Edges = Nodes - 1;
136  PGraph GraphPt = PGraph::New();
137  typename PGraph::TObj& Graph = *GraphPt;
138  Graph.Reserve(Nodes, Edges);
139  int node;
140  for (node = 0; node < Nodes; node++) {
141  Graph.AddNode(node); }
142  // non-leaf nodes
143  for (node = 0; node < (int) Nodes - (int) pow(double(Fanout), double(Levels)); node++) {
144  for (int edge = 1; edge <= Fanout; edge++) {
145  if (IsDir) {
146  if (ChildPointsToParent) { Graph.AddEdge(Fanout*node+edge, node); }
147  else { Graph.AddEdge(node, Fanout*node+edge); }
148  } else {
149  Graph.AddEdge(node, Fanout*node+edge); // link children
150  Graph.AddEdge(Fanout*node+edge, node);
151  }
152  }
153  }
154  return GraphPt;
155 }
156 
162 
170 
173 template <class PGraph>
174 PGraph GenBaraHierar(const int& Levels, const bool& IsDir) {
175  const int Nodes = (int) TMath::Round(TMath::Power(5, Levels));
176  PGraph GraphPt = PGraph::New();
177  typename PGraph::TObj& Graph = *GraphPt;
178  Graph.Reserve(Nodes, -1);
179  // base graph
180  for (int i = 0; i < 5; i++) { Graph.AddNode(i); }
181  Graph.AddEdge(1,2); Graph.AddEdge(2,3);
182  Graph.AddEdge(3,4); Graph.AddEdge(4,1);
183  Graph.AddEdge(1,0); Graph.AddEdge(3,0);
184  Graph.AddEdge(2,0); Graph.AddEdge(4,0);
185  // expansion
186  const int CenterId = 0;
187  for (int lev = 1; lev < Levels+1; lev++) {
188  const int MxNId = Graph.GetNodes();
189  // make 4 duplicate copies
190  for (int d = 0; d < 4; d++) {
191  for (int n = 0; n < MxNId; n++) { Graph.AddNode(); }
192  for (int n = 0; n < MxNId; n++) {
193  typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
194  const int SrcId = n+MxNId*(d+1);
195  for (int e = 0; e < NI.GetOutDeg(); e++) {
196  Graph.AddEdge(SrcId, NI.GetOutNId(e)+MxNId*(d+1));
197  }
198  }
199  }
200  // add edges to the center
201  //const int LevPow = (int)TMath::Round(TMath::Power(5,lev-1));
202  for (int n = MxNId; n < Graph.GetNodes(); n++) {
203  //typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
204  const int SrcId = n;
205  int Pow = 1; bool Skip = false;
206  for (int p = 1; p <= lev; p++) {
207  if (SrcId % (5*Pow) < Pow) { Skip=true; break; }
208  Pow *= 5;
209  }
210  if (Skip) { continue; }
211  Graph.AddEdge(SrcId, CenterId);
212  }
213  }
214  return GraphPt;
215 }
216 
217 template <class PGraph>
218 PGraph GenRndGnm(const int& Nodes, const int& Edges, const bool& IsDir, TRnd& Rnd) {
219  PGraph GraphPt = PGraph::New();
220  typename PGraph::TObj& Graph = *GraphPt;
221  Graph.Reserve(Nodes, Edges);
222  IAssertR((1.0 * (Nodes-1) / 2 * (IsDir ? 2 : 1)) >= (1.0 * Edges / Nodes), TStr::Fmt("Not enough nodes (%d), for edges (%d).", Nodes, Edges));
223  for (int node = 0; node < Nodes; node++) {
224  IAssert(Graph.AddNode(node) == node);
225  }
226  for (int edge = 0; edge < Edges; ) {
227  const int SrcNId = Rnd.GetUniDevInt(Nodes);
228  const int DstNId = Rnd.GetUniDevInt(Nodes);
229  if (SrcNId != DstNId && Graph.AddEdge(SrcNId, DstNId) != -2) { // is new edge
230  if (! IsDir) { Graph.AddEdge(DstNId, SrcNId); }
231  edge++;
232  }
233  }
234  return GraphPt;
235 }
236 
237 namespace TSnapDetail {
239 template <class PGraph>
240 TIntPr GetRndEdgeNonAdjNode(const PGraph& Graph, int NId1, int NId2) {
241  typename PGraph::TObj::TNodeI NI1, NI2;
242  const int NNodes = Graph->GetNodes();
243  int OutDeg = -1;
244  int iter = 0;
245  do {
246  NI1 = Graph->GetRndNI();
247  OutDeg = NI1.GetOutDeg();
248  if (iter++ >= NNodes*2) { return TIntPr(-1, -1); }
249  } while (OutDeg == 0);
250  NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
251  int runs = 0;
252  while (NI1.IsNbrNId(NId1) || NI1.IsNbrNId(NId2) || NI2.IsNbrNId(NId1) || NI2.IsNbrNId(NId2) || NI1.GetId()==NI2.GetId()) {
253  int iter = 0;
254  do {
255  NI1 = Graph->GetRndNI();
256  OutDeg = NI1.GetOutDeg();
257  if (iter++ >= NNodes*2) { return TIntPr(-1, -1); }
258  } while (OutDeg == 0);
259  NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
260  if (runs++ >= 1000) { return TIntPr(-1, -1); }
261  }
262  return TIntPr(NI1.GetId(), NI2.GetId());
263 }
264 
265 } // namespace TSnapDetail
266 
267 }; // namespace TSnap
#define IAssert(Cond)
Definition: bd.h:262
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Main namespace for all the Snap global entities.
Definition: alg.h:1
PGraph GenTree(const int &Fanout, const int &Levels, const bool &IsDir=true, const bool &ChildPointsToParent=true)
Generates a tree graph of Levels levels with every parent having Fanout children. ...
Definition: ggen.h:133
#define IAssertR(Cond, Reason)
Definition: bd.h:265
PNGraph GenRMatEpinions()
Generates a R-Mat graph, with a synthetic copy of the Epinions social network.
Definition: ggen.cpp:550
Definition: dt.h:11
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
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
PGraph GenCircle(const int &Nodes, const int &NodeOutDeg=1, const bool &IsDir=true)
Generates a circle graph where every node creates out-links to NodeOutDeg forward nodes...
Definition: ggen.h:104
PGraph GenStar(const int &Nodes, const bool &IsDir=true)
Generates a graph with star topology. Node id 0 is in the center and then links to all other nodes...
Definition: ggen.h:91
PNGraph GenCopyModel(const int &Nodes, const double &Beta, TRnd &Rnd)
Generates a random scale-free network using the Copying Model.
Definition: ggen.cpp:456
static TRnd Rnd
Definition: dt.h:1146
PBPGraph GenRndBipart(const int &LeftNodes, const int &RightNodes, const int &Edges, TRnd &Rnd)
Generates a random bipartite graph.
Definition: ggen.cpp:5
PGraph GenRndGnm(const int &Nodes, const int &Edges, const bool &IsDir=true, TRnd &Rnd=TInt::Rnd)
Generates an Erdos-Renyi random graph.
Definition: ggen.h:218
PUNGraph GenDegSeq(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random graph with exact degree sequence.
Definition: ggen.cpp:61
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
PGraph GenBaraHierar(const int &Levels, const bool &IsDir=true)
Generates a Ravasz-Barabasi deterministic scale-free graph.
Definition: ggen.h:174
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
static double Round(const double &Val)
Definition: xmath.h:16
static double Power(const double &Base, const double &Exponent)
Definition: xmath.h:25
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
PUNGraph GenConfModel(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random undirect graph with a given degree sequence.
Definition: ggen.cpp:122
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
PGraph GenGrid(const int &Rows, const int &Cols, const bool &IsDir=true)
Generates a 2D-grid graph of Rows rows and Cols columns.
Definition: ggen.h:65
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
Definition: ds.h:32
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
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
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
Definition: bd.h:196
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
PGraph GenFull(const int &Nodes)
Generates a complete graph on Nodes nodes. Graph has no self-loops.
Definition: ggen.h:119