0
# Algorithm Drivers
1

2
Algorithm drivers provide reusable implementations of graph algorithms that can be executed through the Runner framework or used programmatically. Each driver implements the `Driver` interface and supports configurable parameters and multiple output formats.
3

4
## Capabilities
5

6
### Driver Interface
7

8
Base interface for all graph algorithm drivers.
9

10
```java { .api }
11
/**
12
 * A driver for one or more graph algorithms and/or analytics
13
 * Coordinates algorithm execution with input graphs
14
 */
15
public interface Driver<K, VV, EV> extends Parameterized {
16
  /**
17
   * A one-line description presented in algorithm listings
18
   * @return Short description of the algorithm
19
   */
20
  String getShortDescription();
21
  
22
  /**
23
   * A multi-line description presented in algorithm usage help
24
   * @return Detailed description of the algorithm
25
   */
26
  String getLongDescription();
27
  
28
  /**
29
   * Execute algorithms and analytics on the input graph
30
   * The execution plan is finalized in the output methods
31
   * @param graph Input graph to process
32
   * @throws Exception if algorithm execution fails
33
   */
34
  void plan(Graph<K, VV, EV> graph) throws Exception;
35
}
36
```
37

38
### PageRank Driver
39

40
Link analysis algorithm that scores vertices by the number and quality of incoming links.
41

42
```java { .api }
43
/**
44
 * PageRank algorithm driver using iterative computation
45
 * Scores vertices based on link structure and random walk model
46
 */
47
public class PageRank<K, VV, EV> extends SimpleDriver<K, VV, EV, Result<K>> 
48
    implements CSV, Print {
49
  
50
  public String getName();
51
  public String getShortDescription(); // "score vertices by the number and quality of incoming links"
52
  public String getLongDescription();
53
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
54
  public void print(String executionName) throws Exception;
55
}
56
```
57

58
**Configuration Parameters:**
59
- `dampingFactor` (DoubleParameter): Random walk restart probability (default: 0.85, range: 0.0-1.0)
60
- `iterationConvergence` (IterationConvergence): Maximum iterations and convergence threshold (default: 10 iterations)
61

62
**Usage Example:**
63
```bash
64
--algorithm PageRank --dampingFactor 0.9 --iterationConvergence "20;0.001"
65
```
66

67
### Connected Components Driver
68

69
Finds connected components in graphs using the gather-sum-apply (GSA) approach.
70

71
```java { .api }
72
/**
73
 * Connected Components algorithm driver using GSA implementation
74
 * Identifies connected components by propagating minimum vertex IDs
75
 * Requires vertex type to be Comparable for minimum ID computation
76
 */
77
public class ConnectedComponents<K extends Comparable<K>, VV, EV> 
78
    extends ParameterizedBase 
79
    implements Driver<K, VV, EV>, CSV, Hash, Print {
80
  
81
  public String getName();
82
  public String getShortDescription(); // "ConnectedComponents"
83
  public String getLongDescription(); // "ConnectedComponents"
84
  public void plan(Graph<K, VV, EV> graph) throws Exception;
85
  public void hash(String executionName) throws Exception;
86
  public void print(String executionName) throws Exception;
87
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
88
}
89
```
90

91
**Configuration Parameters:** None (uses default GSA configuration)
92

93
**Usage Example:**
94
```bash
95
--algorithm ConnectedComponents
96
```
97

98
### HITS Driver
99

100
Hyperlink-Induced Topic Search algorithm that scores vertices as hubs and authorities.
101

102
```java { .api }
103
/**
104
 * HITS algorithm driver using iterative computation
105
 * Computes hub and authority scores based on link structure
106
 */
107
public class HITS<K, VV, EV> extends SimpleDriver<K, VV, EV, Result<K>> 
108
    implements CSV, Print {
109
  
110
  public String getName();
111
  public String getShortDescription(); // "score vertices as hubs and authorities"
112
  public String getLongDescription();
113
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
114
  public void print(String executionName) throws Exception;
115
}
116
```
117

118
**Configuration Parameters:**
119
- `iterationConvergence` (IterationConvergence): Maximum iterations and convergence threshold (default: 10 iterations)
120

121
**Usage Example:**
122
```bash
123
--algorithm HITS --iterationConvergence "15;0.0001"
124
```
125

126
### Adamic-Adar Driver
127

128
Computes similarity scores between vertices weighted by the degree of common neighbors.
129

130
```java { .api }
131
/**
132
 * Adamic-Adar similarity algorithm driver
133
 * Computes similarity scores weighted by centerpoint degree
134
 */
135
public class AdamicAdar<K extends CopyableValue<K>, VV, EV> 
136
    extends SimpleDriver<K, VV, EV, Result<K>> 
137
    implements CSV, Print {
138
  
139
  public String getName();
140
  public String getShortDescription(); // "similarity score weighted by centerpoint degree"
141
  public String getLongDescription();
142
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
143
  public void print(String executionName) throws Exception;
144
}
145
```
146

147
**Configuration Parameters:**
148
- `minRatio` (DoubleParameter): Minimum ratio threshold for results (default: 0.0, min: 0.0)
149
- `minScore` (DoubleParameter): Minimum score threshold for results (default: 0.0, min: 0.0)
150
- `littleParallelism` (LongParameter): Parallelism setting for small operations
151

152
**Usage Example:**
153
```bash
154
--algorithm AdamicAdar --minRatio 0.1 --minScore 0.5 --littleParallelism 1
155
```
156

157
### Clustering Coefficient Driver
158

159
Computes local clustering coefficients for vertices in the graph.
160

161
```java { .api }
162
/**
163
 * Clustering Coefficient algorithm driver
164
 * Computes local clustering coefficient for each vertex
165
 */
166
public class ClusteringCoefficient<K extends CopyableValue<K>, VV, EV> 
167
    extends SimpleDriver<K, VV, EV, Result<K>> 
168
    implements CSV, Print {
169
  
170
  public String getName();
171
  public String getShortDescription();
172
  public String getLongDescription();
173
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
174
  public void print(String executionName) throws Exception;
175
}
176
```
177

178
**Configuration Parameters:**
179
- `minRatio` (DoubleParameter): Minimum ratio threshold for results
180
- `minScore` (DoubleParameter): Minimum score threshold for results
181
- `littleParallelism` (LongParameter): Parallelism setting
182

183
### Jaccard Index Driver
184

185
Computes Jaccard similarity coefficients between vertex neighborhoods.
186

187
```java { .api }
188
/**
189
 * Jaccard Index similarity algorithm driver
190
 * Computes Jaccard similarity coefficient between vertex pairs
191
 */
192
public class JaccardIndex<K extends CopyableValue<K>, VV, EV> 
193
    extends SimpleDriver<K, VV, EV, Result<K>> 
194
    implements CSV, Print {
195
  
196
  public String getName();
197
  public String getShortDescription();
198
  public String getLongDescription();
199
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
200
  public void print(String executionName) throws Exception;
201
}
202
```
203

204
**Configuration Parameters:**
205
- `minRatio` (DoubleParameter): Minimum ratio threshold for results
206
- `minScore` (DoubleParameter): Minimum score threshold for results
207
- `littleParallelism` (LongParameter): Parallelism setting
208

209
### Triangle Listing Driver
210

211
Enumerates all triangles (3-cycles) in the graph.
212

213
```java { .api }
214
/**
215
 * Triangle Listing algorithm driver
216
 * Enumerates all triangles in the input graph
217
 */
218
public class TriangleListing<K extends CopyableValue<K>, VV, EV> 
219
    extends SimpleDriver<K, VV, EV, Result<K>> 
220
    implements CSV, Hash, Print {
221
  
222
  public String getName();
223
  public String getShortDescription();
224
  public String getLongDescription();
225
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
226
  public void hash(String executionName) throws Exception;
227
  public void print(String executionName) throws Exception;
228
}
229
```
230

231
**Configuration Parameters:**
232
- `minRatio` (DoubleParameter): Minimum ratio threshold for results
233
- `minScore` (DoubleParameter): Minimum score threshold for results
234
- `littleParallelism` (LongParameter): Parallelism setting
235

236
### Graph Metrics Driver
237

238
Computes comprehensive graph metrics for directed or undirected graphs.
239

240
```java { .api }
241
/**
242
 * Graph Metrics algorithm driver
243
 * Computes vertex and edge metrics for graph analysis
244
 */
245
public class GraphMetrics<K extends Comparable<K>, VV, EV> 
246
    extends ParameterizedBase 
247
    implements Driver<K, VV, EV>, Hash, Print {
248
  
249
  public String getName();
250
  public String getShortDescription(); // "compute vertex and edge metrics"
251
  public String getLongDescription();
252
  public void plan(Graph<K, VV, EV> graph) throws Exception;
253
  public void hash(String executionName) throws Exception;
254
  public void print(String executionName) throws Exception;
255
}
256
```
257

258
**Configuration Parameters:**
259
- `order` (ChoiceParameter): Graph type - "directed" or "undirected" (default: "directed")
260
  - "directed": Computes directed graph metrics including in-degree, out-degree distributions
261
  - "undirected": Computes undirected graph metrics including triangle count and clustering coefficient
262

263
**Computed Metrics:**
264
- Vertex count and edge count
265
- Graph density and clustering coefficient
266
- Vertex degree statistics (min, max, average)
267
- Triangle count (undirected graphs)
268
- Additional directed/undirected specific metrics
269

270
**Usage Example:**
271
```bash
272
--algorithm GraphMetrics --order directed
273
```
274

275
### Edge List Driver
276

277
Simple driver that outputs the graph as an edge list for inspection or conversion.
278

279
```java { .api }
280
/**
281
 * Edge List driver for graph output
282
 * Outputs the input graph as a simple edge list
283
 */
284
public class EdgeList<K, VV, EV> extends SimpleDriver<K, VV, EV, Result<K>> 
285
    implements CSV, Hash, Print {
286
  
287
  public String getName();
288
  public String getShortDescription();
289
  public String getLongDescription();
290
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
291
  public void hash(String executionName) throws Exception;
292
  public void print(String executionName) throws Exception;
293
}
294
```
295

296
**Configuration Parameters:** None (direct edge list output)
297

298
## Base Driver Classes
299

300
### SimpleDriver
301

302
Abstract base class for drivers that produce a single result DataSet with integrated output capabilities.
303

304
```java { .api }
305
/**
306
 * Base driver class for algorithms producing a single result DataSet
307
 * Provides common functionality for result handling and output formatting
308
 * Implements standard output interfaces for CSV, Print, and Hash operations
309
 */
310
public abstract class SimpleDriver<K, VV, EV, R extends PrintableResult> 
311
    extends ParameterizedBase implements Driver<K, VV, EV> {
312
  
313
  /**
314
   * Abstract method for algorithm-specific graph processing logic
315
   * Subclasses implement their specific algorithm here
316
   * @param graph Input graph to process
317
   * @return DataSet containing algorithm results
318
   * @throws Exception if algorithm execution fails
319
   */
320
  protected abstract DataSet<R> simplePlan(Graph<K, VV, EV> graph) throws Exception;
321
  
322
  /**
323
   * Get the result DataSet from the last algorithm execution
324
   * @return DataSet containing algorithm results, or null if not executed
325
   */
326
  protected DataSet<R> getResult();
327
  
328
  /**
329
   * Implementation of Driver interface - coordinates algorithm execution
330
   * Calls simplePlan() and stores result for output operations
331
   * @param graph Input graph to process
332
   * @throws Exception if algorithm execution fails
333
   */
334
  public void plan(Graph<K, VV, EV> graph) throws Exception;
335
  
336
  /**
337
   * Compute and print hash of algorithm results for verification
338
   * @param executionName Name to display with hash output
339
   * @throws Exception if hash computation fails
340
   */
341
  public void hash(String executionName) throws Exception;
342
  
343
  /**
344
   * Print algorithm results to console for inspection
345
   * @param executionName Name to display with printed output
346
   * @throws Exception if printing fails
347
   */
348
  public void print(String executionName) throws Exception;
349
  
350
  /**
351
   * Write algorithm results to CSV file with configurable formatting
352
   * @param filename Output file path
353
   * @param lineDelimiter Line separator (e.g., "\n")
354
   * @param fieldDelimiter Field separator (e.g., ",")
355
   * @throws Exception if file writing fails
356
   */
357
  public void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
358
}
359
```
360

361
### ParameterizedBase
362

363
Base class providing common parameter management functionality.
364

365
```java { .api }
366
/**
367
 * Base class for parameterized components
368
 * Provides common parameter parsing and validation functionality
369
 */
370
public abstract class ParameterizedBase implements Parameterized {
371
  
372
  public String getName();
373
  public String getUsage();
374
  public void configure(ParameterTool parameterTool) throws ProgramParametrizationException;
375
  
376
  // Protected methods for parameter management
377
  protected void addParameter(Parameter parameter);
378
  protected String getParametersListing();
379
}
380
```
381

382
## Types
383

384
```java { .api }
385
// Result wrapper for algorithm outputs
386
class Result<K> {
387
  // Contains algorithm-specific result data
388
}
389

390
// Output format interfaces
391
interface CSV {
392
  void writeCSV(String filename, String lineDelimiter, String fieldDelimiter) throws Exception;
393
}
394

395
interface Print {
396
  void print(String executionName) throws Exception;
397
}
398

399
interface Hash {
400
  void hash(String executionName) throws Exception;
401
}
402

403
// Type constraints for certain algorithms
404
interface CopyableValue<T> extends Value {
405
  void copyTo(T target);
406
  T copy();
407
}
408

409
interface Comparable<T> {
410
  int compareTo(T other);
411
}
412
```