Class SAP

LabEnv/06Lab/SAP.java:15–174

import java.util.Arrays;

public class SAP {
    // constructor takes a digraph (not necessarily a DAG)
    private final Digraph g;

    public SAP(Digraph G) {
        if (G == null) throw new IllegalArgumentException();
        g = new Digraph(G);
    }

    private class Helper {
        private int length;
        private int ancestor;

        Helper() {
            length = -1;
            ancestor = -1;
        }

        // query key 0 return length; 1 return id
        private void findSAP(int v, int w) {
            if (v < 0 || v >= g.V() || w < 0 || w >= g.V()) throw new IllegalArgumentException();
            if (v == w) {
                length = 0;
                ancestor = w;
                return;
            }
            int[] dist1 = new int[g.V()];
            int[] dist2 = new int[g.V()];
            Arrays.fill(dist1, -1);
            Arrays.fill(dist2, -1);
            // run BFS from v, log every ancestor's distance to v
            Queue<Integer> todo = new Queue<>();
            todo.enqueue(v);
            dist1[v] = 0;
            while (!todo.isEmpty()) {
                int p = todo.dequeue();
                for (int q : g.adj(p)) {
                    if (dist1[q] < 0) { // unmarked (unvisited)
                        dist1[q] = dist1[p] + 1;
                        todo.enqueue(q);
                    }
                }
            }
            int min = Integer.MAX_VALUE;
            // run BFS from w
            dist2[w] = 0;
            todo.enqueue(w);
            while (!todo.isEmpty()) {
                int p = todo.dequeue();
                // find result, dist1[q] >= 0 means first BFS visited
                if (dist1[p] >= 0 && dist1[p] + dist2[p] < min) {
                    min = dist1[p] + dist2[p];
                    ancestor = p;
                }
                for (int q : g.adj(p)) {
                    if (dist2[q] < 0) { // unmarked (unvisited)
                        dist2[q] = dist2[p] + 1;
                        todo.enqueue(q);