0
# Graph Generators
1

2
Gelly provides comprehensive graph generation utilities for creating synthetic graphs for testing, benchmarking, and algorithm development. The generators support various graph topologies and probability distributions, enabling creation of graphs with specific structural properties.
3

4
## Capabilities
5

6
### Generator Base Class
7

8
All graph generators extend the abstract base class providing common functionality.
9

10
```java { .api }
11
public abstract class AbstractGraphGenerator<K, VV, EV> {
12
    public abstract Graph<K, VV, EV> generate() throws Exception;
13
    
14
    public AbstractGraphGenerator<K, VV, EV> setParallelism(int parallelism)
15
    protected ExecutionEnvironment getExecutionEnvironment()
16
}
17
```
18

19
### Generator Utilities
20

21
Common utilities and helper functions for graph generation.
22

23
```java { .api }
24
public class GraphGeneratorUtils {
25
    // Utility methods for graph generation
26
    public static <T> DataSet<T> parallelizeArray(ExecutionEnvironment env, T[] array, int parallelism)
27
    // Additional utility methods
28
}
29
```
30

31
### Complete Graphs
32

33
Generate complete graphs where every vertex is connected to every other vertex.
34

35
```java { .api }
36
public class CompleteGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV> {
37
    public CompleteGraph(ExecutionEnvironment env, long numVertices)
38
}
39
```
40

41
**Usage Example:**
42

43
```java
44
ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
45

46
// Create complete graph with 10 vertices
47
CompleteGraph<LongValue, NullValue, NullValue> completeGen = 
48
    new CompleteGraph<>(env, 10L);
49

50
Graph<LongValue, NullValue, NullValue> complete = completeGen.generate();
51

52
// Complete graph properties:
53
// - 10 vertices (0, 1, 2, ..., 9)
54
// - 45 edges (n*(n-1)/2 for undirected)
55
// - Every vertex connected to every other vertex
56

57
System.out.println("Vertices: " + complete.numberOfVertices()); // 10
58
System.out.println("Edges: " + complete.numberOfEdges());       // 45
59
```
60

61
### Empty Graphs
62

63
Generate graphs with vertices but no edges.
64

65
```java { .api }
66
public class EmptyGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV> {
67
    public EmptyGraph(ExecutionEnvironment env, long numVertices)
68
}
69
```
70

71
**Usage Example:**
72

73
```java
74
// Create empty graph with 5 vertices and no edges
75
EmptyGraph<LongValue, NullValue, NullValue> emptyGen = 
76
    new EmptyGraph<>(env, 5L);
77

78
Graph<LongValue, NullValue, NullValue> empty = emptyGen.generate();
79

80
System.out.println("Vertices: " + empty.numberOfVertices()); // 5
81
System.out.println("Edges: " + empty.numberOfEdges());       // 0
82
```
83

84
### Path Graphs
85

86
Generate linear path graphs where vertices form a single chain.
87

88
```java { .api }
89
public class PathGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV> {
90
    public PathGraph(ExecutionEnvironment env, long numVertices)
91
}
92
```
93

94
**Usage Example:**
95

96
```java
97
// Create path graph: 0-1-2-3-4
98
PathGraph<LongValue, NullValue, NullValue> pathGen = 
99
    new PathGraph<>(env, 5L);
100

101
Graph<LongValue, NullValue, NullValue> path = pathGen.generate();
102

103
// Path graph properties:
104
// - 5 vertices: 0, 1, 2, 3, 4
105
// - 4 edges: (0,1), (1,2), (2,3), (3,4)
106
// - Forms a single linear chain
107

108
System.out.println("Vertices: " + path.numberOfVertices()); // 5
109
System.out.println("Edges: " + path.numberOfEdges());       // 4
110
```
111

112
### Hypercube Graphs
113

114
Generate n-dimensional hypercube graphs.
115

116
```java { .api }
117
public class HypercubeGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV> {
118
    public HypercubeGraph(ExecutionEnvironment env, long dimensions)
119
}
120
```
121

122
**Usage Example:**
123

124
```java
125
// Create 3-dimensional hypercube (cube)
126
HypercubeGraph<LongValue, NullValue, NullValue> cubeGen = 
127
    new HypercubeGraph<>(env, 3L);
128

129
Graph<LongValue, NullValue, NullValue> cube = cubeGen.generate();
130

131
// 3D hypercube properties:
132
// - 8 vertices (2^3)
133
// - 12 edges (3 * 2^2)
134
// - Each vertex connected to 3 neighbors (differs in 1 bit)
135

136
System.out.println("Vertices: " + cube.numberOfVertices()); // 8
137
System.out.println("Edges: " + cube.numberOfEdges());       // 12
138
```
139

140
### Single Edge Graphs
141

142
Generate graphs with exactly one edge between two vertices.
143

144
```java { .api }
145
public class SingletonEdgeGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV> {
146
    public SingletonEdgeGraph(ExecutionEnvironment env, K source, K target, EV edgeValue)
147
}
148
```
149

150
**Usage Example:**
151

152
```java
153
// Create graph with single edge from vertex 1 to vertex 2
154
SingletonEdgeGraph<LongValue, NullValue, DoubleValue> singletonGen = 
155
    new SingletonEdgeGraph<>(env, 
156
        new LongValue(1L), 
157
        new LongValue(2L), 
158
        new DoubleValue(1.5));
159

160
Graph<LongValue, NullValue, DoubleValue> singleton = singletonGen.generate();
161

162
System.out.println("Vertices: " + singleton.numberOfVertices()); // 2
163
System.out.println("Edges: " + singleton.numberOfEdges());       // 1
164
```
165

166
### Echo Graphs
167

168
Generate echo graphs where each vertex has a self-loop.
169

170
```java { .api }
171
public class EchoGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV> {
172
    public EchoGraph(ExecutionEnvironment env, long numVertices)
173
}
174
```
175

176
**Usage Example:**
177

178
```java
179
// Create echo graph with self-loops
180
EchoGraph<LongValue, NullValue, NullValue> echoGen = 
181
    new EchoGraph<>(env, 4L);
182

183
Graph<LongValue, NullValue, NullValue> echo = echoGen.generate();
184

185
// Echo graph properties:
186
// - 4 vertices: 0, 1, 2, 3
187
// - 4 self-loop edges: (0,0), (1,1), (2,2), (3,3)
188

189
System.out.println("Vertices: " + echo.numberOfVertices()); // 4
190
System.out.println("Edges: " + echo.numberOfEdges());       // 4
191
```
192

193
## Random Graph Generators
194

195
Generators for creating random graphs with various probability distributions and structural properties.
196

197
### Random Graph Types
198

199
The `org.apache.flink.graph.generator.random` package contains various random graph generators:
200

201
```java { .api }
202
// Example random generators (specific classes may vary)
203
public class ErdosRenyiGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV>
204
public class BarabasiAlbertGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV>
205
public class WattsStrogatzGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV>
206
public class RMatGraph<K, VV, EV> extends AbstractGraphGenerator<K, VV, EV>
207
```
208

209
### Erdős–Rényi Random Graphs
210

211
Generate random graphs where each possible edge exists with a given probability.
212

213
**Usage Example:**
214

215
```java
216
// Create Erdős–Rényi graph with 100 vertices and edge probability 0.1
217
ErdosRenyiGraph<LongValue, NullValue, NullValue> erGen = 
218
    new ErdosRenyiGraph<>(env, 100L, 0.1);
219

220
Graph<LongValue, NullValue, NullValue> randomGraph = erGen.generate();
221

222
// Expected properties:
223
// - 100 vertices
224
// - ~495 edges (binomial distribution around n*(n-1)/2 * p)
225
// - Random connectivity structure
226
```
227

228
### Scale-Free Networks
229

230
Generate scale-free networks using various models.
231

232
**Usage Example:**
233

234
```java
235
// Create Barabási–Albert scale-free network
236
BarabasiAlbertGraph<LongValue, NullValue, NullValue> baGen = 
237
    new BarabasiAlbertGraph<>(env, 1000L, 3); // 1000 vertices, 3 edges per new vertex
238

239
Graph<LongValue, NullValue, NullValue> scaleFreee = baGen.generate();
240

241
// Scale-free properties:
242
// - Power-law degree distribution
243
// - Hub vertices with very high degree
244
// - Most vertices with low degree
245
```
246

247
## Advanced Generator Usage
248

249
### Custom Vertex and Edge Values
250

251
Generators can be configured with custom vertex and edge value initializers.
252

253
**Usage Example:**
254

255
```java
256
// Complete graph with custom vertex values
257
CompleteGraph<LongValue, StringValue, DoubleValue> customGen = 
258
    new CompleteGraph<LongValue, StringValue, DoubleValue>(env, 5L) {
259
    
260
    @Override
261
    protected StringValue getVertexValue(LongValue vertexId) {
262
        return new StringValue("vertex_" + vertexId.getValue());
263
    }
264
    
265
    @Override  
266
    protected DoubleValue getEdgeValue(LongValue source, LongValue target) {
267
        return new DoubleValue(Math.random());
268
    }
269
};
270

271
Graph<LongValue, StringValue, DoubleValue> customGraph = customGen.generate();
272
```
273

274
### Parallelism Configuration
275

276
Set parallelism for distributed graph generation.
277

278
**Usage Example:**
279

280
```java
281
// Generate large complete graph with high parallelism
282
CompleteGraph<LongValue, NullValue, NullValue> largeGen = 
283
    new CompleteGraph<>(env, 10000L);
284

285
largeGen.setParallelism(16); // Use 16 parallel tasks
286

287
Graph<LongValue, NullValue, NullValue> largeGraph = largeGen.generate();
288
```
289

290
### Combining Generators
291

292
Combine multiple generators to create complex graph structures.
293

294
**Usage Example:**
295

296
```java
297
// Create composite graph structure
298
Graph<LongValue, NullValue, NullValue> path = new PathGraph<>(env, 5L).generate();
299
Graph<LongValue, NullValue, NullValue> complete = new CompleteGraph<>(env, 3L).generate();
300

301
// Translate IDs to avoid conflicts
302
Graph<LongValue, NullValue, NullValue> translatedComplete = complete
303
    .translateGraphIds(new LongValueAddOffset(new LongValue(10L)));
304

305
// Union the graphs
306
Graph<LongValue, NullValue, NullValue> composite = path.union(translatedComplete);
307

308
System.out.println("Composite vertices: " + composite.numberOfVertices()); // 8
309
System.out.println("Composite edges: " + composite.numberOfEdges());       // 7
310
```
311

312
## Performance Considerations
313

314
### Memory Usage
315

316
Large graph generation can be memory-intensive:
317

318
```java
319
// Configure memory for large graph generation
320
ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
321
env.getConfig().setTaskManagerMemory(4096); // 4GB
322

323
// Generate large graph
324
CompleteGraph<LongValue, NullValue, NullValue> gen = 
325
    new CompleteGraph<>(env, 50000L); // Will create ~1.25B edges
326

327
gen.setParallelism(32); // High parallelism for distribution
328
```
329

330
### Data Type Selection
331

332
Choose appropriate data types for performance:
333

334
```java
335
// Efficient types for large graphs
336
Graph<LongValue, NullValue, NullValue> efficientGraph = /* generator */;
337

338
// Less efficient for large-scale generation
339
Graph<String, ComplexObject, ComplexEdgeValue> inefficientGraph = /* generator */;
340
```
341

342
### Generation Patterns
343

344
```java
345
// Efficient: Generate once, reuse
346
CompleteGraph<LongValue, NullValue, NullValue> generator = new CompleteGraph<>(env, 1000L);
347
Graph<LongValue, NullValue, NullValue> baseGraph = generator.generate();
348

349
// Create variations
350
Graph<LongValue, StringValue, NullValue> variation1 = baseGraph.mapVertices(v -> new StringValue("v" + v.getId()));
351
Graph<LongValue, NullValue, DoubleValue> variation2 = baseGraph.mapEdges(e -> new DoubleValue(1.0));
352

353
// Inefficient: Multiple generation calls
354
// CompleteGraph<LongValue, NullValue, NullValue> gen1 = new CompleteGraph<>(env, 1000L);
355
// CompleteGraph<LongValue, NullValue, NullValue> gen2 = new CompleteGraph<>(env, 1000L);
356
// Graph<LongValue, NullValue, NullValue> graph1 = gen1.generate();
357
// Graph<LongValue, NullValue, NullValue> graph2 = gen2.generate();
358
```