Java graph exercises: verify reachability before trusting component labels

Java 8+. The program uses JDK classes and requires no preview flags.

Start with a small reference model

For a small graph, a boolean reachability matrix is useful as a reference. It includes zero-length self-reachability, records direct edges, and closes the relation through each intermediate vertex. Mutual reachability then defines whether two vertices belong to one strong component.

The completed exercise asks for a cycle group, a one-way edge and an isolated vertex. It verifies both directions when claiming a shared component. Merely observing that the first vertex can reach the second is insufficient.

Use this reference on small inputs to check the faster adjacency-list implementation. Its cubic work is acceptable in a bounded test, not a reason to choose a dense matrix for every large sparse application graph.

Change the fixture deliberately

Add a reverse edge and predict which component groups will merge before running the program. Add an invalid endpoint and require rejection before returning a result. Keep assertions that test graph meaning rather than one incidental ordering of labels.

Working program

public class ReachabilityExercise {
    static boolean[][] closure(int[][] edges){
        int n=edges.length;if(n>100)throw new IllegalArgumentException("Exercise graph budget");boolean[][] reachable=new boolean[n][n];
        for(int i=0;i<n;i++){reachable[i][i]=true;if(edges[i]==null)throw new IllegalArgumentException("Missing adjacency");for(int to:edges[i]){if(to<0||to>=n)throw new IllegalArgumentException("Endpoint");reachable[i][to]=true;}}
        for(int via=0;via<n;via++)for(int from=0;from<n;from++)for(int to=0;to<n;to++)reachable[from][to]|=reachable[from][via]&&reachable[via][to];return reachable;
    }
    static void require(boolean expected){if(!expected)throw new AssertionError("Reachability exercise");}
    public static void main(String[] args){
        boolean[][] r=closure(new int[][]{{1},{0,2},{},{}});
        require(r[0][1]&&r[1][0]);require(r[0][2]&&!r[2][0]);require(r[3][3]&&!r[3][0]);System.out.println("checks=3");
    }
}

Output

checks=3

Costs and boundaries

The reference takes O(V³) time and O(V²) memory. It is deliberately limited to small test graphs. Reachability does not contain minimum path costs, and a self-reachable vertex does not by itself prove a nonempty cycle.

Common Mistakes

• Mutual reachability needs both directions.
• Self-reachability includes the zero-length path.
• Traversal labels are not the relation being tested.

Read next

Linear traversal partition, Weighted all-pairs paths.