Utility Classes

/**
 * Provides generators for several different test graphs suitable for 
 * testing graph algorithms and demonstrating graph structures.
 */
public class TestGraphs {
    
    /**
     * A series of pairs useful for generating graphs (8 edges, 10 nodes, two connected components)
     */
    public static String[][] pairs;
    
    /**
     * Creates a small sample graph for testing purposes
     * @param directed If true, creates directed graph; if false, creates undirected graph
     * @return Small test graph with predefined structure
     */
    public static Graph<String, Number> createTestGraph(boolean directed);
    
    /**
     * Creates a graph with a chain of vertices and isolated vertices
     * @param chain_length Number of vertices in the chain
     * @param isolate_count Number of isolated vertices to add
     * @return Graph with linear chain plus isolated vertices
     */
    public static Graph<String,Number> createChainPlusIsolates(int chain_length, int isolate_count);
    
    /**
     * Creates a sample directed acyclic graph with multiple layers
     * @param layers Number of layers in the DAG
     * @param maxNodesPerLayer Maximum number of nodes in each layer
     * @param linkprob Probability of creating edges between adjacent layers
     * @return Layered directed acyclic graph
     */
    public static Graph<String,Number> createDirectedAcyclicGraph(int layers, int maxNodesPerLayer, double linkprob);
    
    /**
     * Returns a bigger, undirected test graph with just one component
     * @return Single-component undirected graph for testing
     */
    public static Graph<String,Number> getOneComponentGraph();
    
    /**
     * Returns a bigger test graph with a clique, several components, and other parts
     * @return Complex test graph with multiple structural features
     */
    public static Graph<String, Number> getDemoGraph();
    
    /**
     * Returns a small graph with directed and undirected edges, and parallel edges
     * @return Mixed-type test graph demonstrating various edge types
     */
    public static Graph<String, Number> getSmallGraph();
    
    // Private helper method
    private static void createEdge(Graph<String, Number> g, String v1Label, String v2Label, int weight);
}

import edu.uci.ics.jung.graph.util.TestGraphs;
import edu.uci.ics.jung.graph.Graph;

// Create basic test graphs
Graph<String, Number> directedTest = TestGraphs.createTestGraph(true);   // Directed test graph
Graph<String, Number> undirectedTest = TestGraphs.createTestGraph(false); // Undirected test graph

System.out.println("Directed test graph:");
System.out.println("Vertices: " + directedTest.getVertices());
System.out.println("Edges: " + directedTest.getEdges());

// Create chain with isolated vertices
Graph<String, Number> chainGraph = TestGraphs.createChainPlusIsolates(5, 3);
// Creates: V0-V1-V2-V3-V4 (chain) plus V5, V6, V7 (isolated)

System.out.println("Chain graph vertices: " + chainGraph.getVertexCount()); // 8 total
System.out.println("Chain graph edges: " + chainGraph.getEdgeCount());     // 4 edges in chain

// Create directed acyclic graph (DAG)
Graph<String, Number> dag = TestGraphs.createDirectedAcyclicGraph(
    4,      // 4 layers
    3,      // max 3 nodes per layer  
    0.5     // 50% probability of edges between layers
);

System.out.println("DAG structure:");
System.out.println("Vertices: " + dag.getVertices());
System.out.println("Edges: " + dag.getEdges());

// Get predefined complex graphs
Graph<String, Number> oneComponent = TestGraphs.getOneComponentGraph();
Graph<String, Number> demo = TestGraphs.getDemoGraph();
Graph<String, Number> mixed = TestGraphs.getSmallGraph();

// Analyze graph properties
System.out.println("One component graph - Vertices: " + oneComponent.getVertexCount());
System.out.println("Demo graph - Components and features: " + demo.getVertexCount() + " vertices");
System.out.println("Mixed graph - Edge types: " + mixed.getEdgeCount() + " edges");

Graph<String, Number> testGraph = TestGraphs.createTestGraph(false);

// Typical structure includes:
// - Multiple connected components
// - Various vertex degrees
// - Predictable structure for verification

Graph<String, Number> chain = TestGraphs.createChainPlusIsolates(4, 2);

// Structure: V0-V1-V2-V3 (connected chain) + V4, V5 (isolated)
// Useful for testing:
// - Connected component algorithms
// - Graph traversal behavior with disconnected vertices
// - Isolation detection algorithms

Graph<String, Number> dag = TestGraphs.createDirectedAcyclicGraph(3, 4, 0.7);

// Creates 3 layers with up to 4 vertices each
// 70% probability of edges between adjacent layers
// Guarantees acyclic property
// Useful for:
// - Topological sorting algorithms
// - Dependency resolution testing
// - Scheduling algorithm verification

Graph<String, Number> connected = TestGraphs.getOneComponentGraph();

// Features:
// - All vertices reachable from any starting vertex
// - Various local structures (paths, cycles, branches)
// - Suitable for testing connectivity algorithms

Graph<String, Number> demo = TestGraphs.getDemoGraph();

// Includes:
// - Cliques (fully connected subgraphs)
// - Multiple components
// - Various structural patterns
// - Comprehensive test case for complex algorithms

Graph<String, Number> mixed = TestGraphs.getSmallGraph();

// Features:
// - Directed edges
// - Undirected edges  
// - Parallel edges (if using multigraph)
// - Compact size for debugging mixed-graph algorithms

// Test graph algorithms with various structures
Graph<String, Number> testCase = TestGraphs.createTestGraph(true);

// Run your algorithm
MyGraphAlgorithm algorithm = new MyGraphAlgorithm();
Result result = algorithm.process(testCase);

// Verify expected behavior on known structure
assert result.isValid() : "Algorithm failed on test graph";

// Create graphs of different sizes for performance testing
Graph<String, Number> small = TestGraphs.createChainPlusIsolates(10, 5);
Graph<String, Number> medium = TestGraphs.createDirectedAcyclicGraph(5, 10, 0.3);
Graph<String, Number> large = TestGraphs.getOneComponentGraph();

// Measure algorithm performance across different graph sizes
long startTime = System.currentTimeMillis();
algorithm.process(large);
long endTime = System.currentTimeMillis();
System.out.println("Processing time: " + (endTime - startTime) + "ms");

// Demonstrate different graph properties
Graph<String, Number> dag = TestGraphs.createDirectedAcyclicGraph(3, 3, 0.5);
System.out.println("DAG has " + dag.getVertexCount() + " vertices");

// Show connectivity properties
Graph<String, Number> disconnected = TestGraphs.createChainPlusIsolates(3, 2);
System.out.println("Graph has isolated vertices: " + hasIsolatedVertices(disconnected));

// Use consistent test graphs for regression testing
public void testMyAlgorithm() {
    Graph<String, Number> standardTest = TestGraphs.createTestGraph(false);
    
    Result result = myAlgorithm.process(standardTest);
    
    // Verify against known good results
    assertEquals(expectedVertexCount, result.getProcessedVertices());
    assertEquals(expectedEdgeCount, result.getProcessedEdges());
}

// Works with any JUNG graph type
DirectedGraph<String, Number> directed = new DirectedSparseGraph<>();
Graph<String, Number> testData = TestGraphs.createTestGraph(true);

// Copy test structure to your graph type
for (String vertex : testData.getVertices()) {
    directed.addVertex(vertex);
}
for (Number edge : testData.getEdges()) {
    Pair<String> endpoints = testData.getEndpoints(edge);
    directed.addEdge(edge, endpoints.getFirst(), endpoints.getSecond());
}