0
# Graph Algorithms
1

2
Collection of graph processing algorithms implementing the standardized Driver interface. Each algorithm provides configurable parameters, analytics reporting, and consistent execution patterns.
3

4
## Capabilities
5

6
### Driver Interface
7

8
Base interface that all graph algorithms must implement, providing standardized algorithm description, execution, and analytics.
9

10
```java { .api }
11
/**
12
 * Base interface for all graph processing algorithms
13
 * @param <K> Vertex key type
14
 * @param <VV> Vertex value type  
15
 * @param <EV> Edge value type
16
 */
17
public interface Driver<K, VV, EV> extends Parameterized {
18
    /** One-line algorithm description for command-line listings */
19
    String getShortDescription();
20
    
21
    /** Multi-line detailed algorithm description with usage information */
22
    String getLongDescription();
23
    
24
    /** Execute the algorithm on the input graph */
25
    DataSet plan(Graph<K, VV, EV> graph) throws Exception;
26
    
27
    /** Print algorithm-specific analytics and results to console */
28
    void printAnalytics(PrintStream out);
29
}
30
```
31

32
### Driver Base Class
33

34
Base implementation providing common functionality for algorithm drivers.
35

36
```java { .api }
37
/**
38
 * Base class for algorithm drivers with common parameter handling
39
 */
40
public abstract class DriverBase<K, VV, EV> extends ParameterizedBase implements Driver<K, VV, EV> {
41
    /** Execution parallelism configuration */
42
    LongParameter parallelism;
43
    
44
    /** Default analytics implementation (no-op) */
45
    public void printAnalytics(PrintStream out);
46
}
47
```
48

49
### PageRank Algorithm
50

51
Computes PageRank centrality scores using power iteration method with configurable damping factor and convergence criteria.
52

53
```java { .api }
54
/**
55
 * PageRank centrality algorithm with configurable parameters
56
 */
57
public class PageRank extends DriverBase<K, VV, EV> {
58
    /** PageRank damping factor (default: 0.85) */
59
    DoubleParameter dampingFactor;
60
    
61
    /** Iteration convergence control */
62
    IterationConvergence iterationConvergence;
63
    
64
    /** Include zero-degree vertices in results */
65
    BooleanParameter includeZeroDegreeVertices;
66
}
67
```
68

69
**Usage Examples:**
70

71
```bash
72
# Basic PageRank execution
73
--algorithm PageRank --damping_factor 0.85 --iterations 10
74

75
# PageRank with convergence threshold
76
--algorithm PageRank --damping_factor 0.9 --convergence_threshold 0.001
77
```
78

79
### Connected Components
80

81
Finds connected components in undirected graphs using iterative label propagation.
82

83
```java { .api }
84
/**
85
 * Connected components algorithm for finding graph connectivity
86
 */
87
public class ConnectedComponents extends DriverBase<K, VV, EV> {
88
    // Inherits parallelism parameter from DriverBase
89
}
90
```
91

92
**Usage Examples:**
93

94
```bash
95
# Find connected components
96
--algorithm ConnectedComponents
97

98
# With custom parallelism
99
--algorithm ConnectedComponents --parallelism 4
100
```
101

102
### HITS Algorithm
103

104
Computes Hub and Authority scores using Hyperlink-Induced Topic Search algorithm.
105

106
```java { .api }
107
/**
108
 * HITS (Hyperlink-Induced Topic Search) algorithm
109
 * Computes hub and authority scores for directed graphs
110
 */
111
public class HITS extends DriverBase<K, VV, EV> {
112
    // Implementation details handled by base class parameters
113
}
114
```
115

116
### Clustering Coefficient
117

118
Computes local and global clustering coefficients measuring graph transitivity.
119

120
```java { .api }
121
/**
122
 * Clustering coefficient computation for measuring graph clustering
123
 */
124
public class ClusteringCoefficient extends DriverBase<K, VV, EV> {
125
    // Computes both local coefficients per vertex and global coefficient
126
}
127
```
128

129
### Triangle Listing
130

131
Enumerates all triangles (3-cycles) in the graph for structural analysis.
132

133
```java { .api }
134
/**
135
 * Triangle listing algorithm for finding all triangles in graph
136
 */
137
public class TriangleListing extends DriverBase<K, VV, EV> {
138
    // Lists all triangles as triplets of vertices
139
}
140
```
141

142
### Similarity Measures
143

144
#### Adamic-Adar Index
145

146
Computes Adamic-Adar similarity scores for link prediction and graph analysis.
147

148
```java { .api }
149
/**
150
 * Adamic-Adar similarity measure for link prediction
151
 */
152
public class AdamicAdar extends DriverBase<K, VV, EV> {
153
    // Computes similarity based on common neighbors weighted by neighbor degree
154
}
155
```
156

157
#### Jaccard Index
158

159
Computes Jaccard similarity coefficients between vertices based on common neighbors.
160

161
```java { .api }
162
/**
163
 * Jaccard similarity index for measuring vertex similarity
164
 */
165
public class JaccardIndex extends DriverBase<K, VV, EV> {
166
    // Computes Jaccard coefficient: |intersection| / |union|
167
}
168
```
169

170
### Graph Metrics
171

172
Computes comprehensive graph statistics and structural metrics.
173

174
```java { .api }
175
/**
176
 * Comprehensive graph metrics computation
177
 * Provides detailed statistics about graph structure
178
 */
179
public class GraphMetrics extends DriverBase<K, VV, EV> {
180
    // Computes vertex count, edge count, degree distribution, etc.
181
}
182
```
183

184
### Edge List Generation
185

186
Generates simple edge list representation of the graph.
187

188
```java { .api }
189
/**
190
 * Edge list generator for exporting graph structure
191
 */
192
public class EdgeList extends DriverBase<K, VV, EV> {
193
    // Outputs graph as list of edges
194
}
195
```
196

197
## Algorithm-Specific Types
198

199
### Iteration Convergence Control
200

201
```java { .api }
202
/**
203
 * Controls iterative algorithm convergence behavior
204
 */
205
public class IterationConvergence extends ParameterizedBase {
206
    /** Maximum number of iterations */
207
    LongParameter iterations;
208
    
209
    /** Convergence threshold for early termination */
210
    DoubleParameter convergenceThreshold;
211
    
212
    /** Enable convergence threshold checking */
213
    BooleanParameter convergenceEnabled;
214
}
215
```
216

217
### Usage Patterns
218

219
**Basic Algorithm Execution:**
220

221
```java
222
// Create and configure algorithm
223
PageRank pageRank = new PageRank();
224
pageRank.configure(parameterTool);
225

226
// Execute on graph
227
DataSet result = pageRank.plan(inputGraph);
228

229
// Print analytics
230
pageRank.printAnalytics(System.out);
231
```
232

233
**Algorithm Selection by Name:**
234

235
```java
236
// Get algorithm from factory
237
ParameterizedFactory<Driver> factory = createDriverFactory();
238
Driver algorithm = factory.get("PageRank");
239

240
if (algorithm != null) {
241
    algorithm.configure(parameters);
242
    DataSet result = algorithm.plan(graph);
243
    algorithm.printAnalytics(System.out);
244
}
245
```
246

247
**Algorithm Listing:**
248

249
```java
250
// List all available algorithms
251
ParameterizedFactory<Driver> factory = createDriverFactory();
252
for (Driver algorithm : factory) {
253
    System.out.println(algorithm.getName() + ": " + algorithm.getShortDescription());
254
}
255
```