Graph Algorithms

/**
 * Base interface for all graph processing algorithms
 * @param <K> Vertex key type
 * @param <VV> Vertex value type  
 * @param <EV> Edge value type
 */
public interface Driver<K, VV, EV> extends Parameterized {
    /** One-line algorithm description for command-line listings */
    String getShortDescription();
    
    /** Multi-line detailed algorithm description with usage information */
    String getLongDescription();
    
    /** Execute the algorithm on the input graph */
    DataSet plan(Graph<K, VV, EV> graph) throws Exception;
    
    /** Print algorithm-specific analytics and results to console */
    void printAnalytics(PrintStream out);
}

/**
 * Base class for algorithm drivers with common parameter handling
 */
public abstract class DriverBase<K, VV, EV> extends ParameterizedBase implements Driver<K, VV, EV> {
    /** Execution parallelism configuration */
    LongParameter parallelism;
    
    /** Default analytics implementation (no-op) */
    public void printAnalytics(PrintStream out);
}

/**
 * PageRank centrality algorithm with configurable parameters
 */
public class PageRank extends DriverBase<K, VV, EV> {
    /** PageRank damping factor (default: 0.85) */
    DoubleParameter dampingFactor;
    
    /** Iteration convergence control */
    IterationConvergence iterationConvergence;
    
    /** Include zero-degree vertices in results */
    BooleanParameter includeZeroDegreeVertices;
}

# Basic PageRank execution
--algorithm PageRank --damping_factor 0.85 --iterations 10

# PageRank with convergence threshold
--algorithm PageRank --damping_factor 0.9 --convergence_threshold 0.001

/**
 * Connected components algorithm for finding graph connectivity
 */
public class ConnectedComponents extends DriverBase<K, VV, EV> {
    // Inherits parallelism parameter from DriverBase
}

# Find connected components
--algorithm ConnectedComponents

# With custom parallelism
--algorithm ConnectedComponents --parallelism 4

/**
 * HITS (Hyperlink-Induced Topic Search) algorithm
 * Computes hub and authority scores for directed graphs
 */
public class HITS extends DriverBase<K, VV, EV> {
    // Implementation details handled by base class parameters
}

/**
 * Clustering coefficient computation for measuring graph clustering
 */
public class ClusteringCoefficient extends DriverBase<K, VV, EV> {
    // Computes both local coefficients per vertex and global coefficient
}

/**
 * Triangle listing algorithm for finding all triangles in graph
 */
public class TriangleListing extends DriverBase<K, VV, EV> {
    // Lists all triangles as triplets of vertices
}

/**
 * Adamic-Adar similarity measure for link prediction
 */
public class AdamicAdar extends DriverBase<K, VV, EV> {
    // Computes similarity based on common neighbors weighted by neighbor degree
}

/**
 * Jaccard similarity index for measuring vertex similarity
 */
public class JaccardIndex extends DriverBase<K, VV, EV> {
    // Computes Jaccard coefficient: |intersection| / |union|
}

/**
 * Comprehensive graph metrics computation
 * Provides detailed statistics about graph structure
 */
public class GraphMetrics extends DriverBase<K, VV, EV> {
    // Computes vertex count, edge count, degree distribution, etc.
}

/**
 * Edge list generator for exporting graph structure
 */
public class EdgeList extends DriverBase<K, VV, EV> {
    // Outputs graph as list of edges
}

/**
 * Controls iterative algorithm convergence behavior
 */
public class IterationConvergence extends ParameterizedBase {
    /** Maximum number of iterations */
    LongParameter iterations;
    
    /** Convergence threshold for early termination */
    DoubleParameter convergenceThreshold;
    
    /** Enable convergence threshold checking */
    BooleanParameter convergenceEnabled;
}

// Create and configure algorithm
PageRank pageRank = new PageRank();
pageRank.configure(parameterTool);

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

// Print analytics
pageRank.printAnalytics(System.out);

// Get algorithm from factory
ParameterizedFactory<Driver> factory = createDriverFactory();
Driver algorithm = factory.get("PageRank");

if (algorithm != null) {
    algorithm.configure(parameters);
    DataSet result = algorithm.plan(graph);
    algorithm.printAnalytics(System.out);
}

// List all available algorithms
ParameterizedFactory<Driver> factory = createDriverFactory();
for (Driver algorithm : factory) {
    System.out.println(algorithm.getName() + ": " + algorithm.getShortDescription());
}