SNAP Library 4.0, Developer 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.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
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:547
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: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
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:453
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
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: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
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:442
PUNGraph GenConfModel(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random undirect graph with a given degree sequence.
Definition: ggen.cpp:119
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
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:412
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:361
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