SAP.java

import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;

import java.util.ArrayList;

public class SAP {

    private final Digraph G;
    private final int range;

    // constructor takes a digraph (not necessarily a DAG)
    public SAP(Digraph G) {
        if (G == null) {
            throw new NullPointerException();
        }
        this.G = new Digraph(G);
        this.range = this.G.V();
    }

    // length of shortest ancestral path between v and w; -1 if no such path
    public int length(int v, int w) {
        validate(v);
        validate(w);
        if (v == w) return 0;
        ArrayList<Integer> vIterable = new ArrayList<>();
        vIterable.add(v);
        ArrayList<Integer> wIterable = new ArrayList<>();
        wIterable.add(w);
        return deluxeBfs(vIterable, wIterable)[1];
    }

    // a common ancestor of v and w that participates in a shortest ancestral path; -1 if no such path
    public int ancestor(int v, int w) {
        validate(v);
        validate(w);
        if (v == w) return v;
        ArrayList<Integer> vIterable = new ArrayList<>();
        vIterable.add(v);
        ArrayList<Integer> wIterable = new ArrayList<>();
        wIterable.add(w);
        return deluxeBfs(vIterable, wIterable)[0];
    }

    // length of shortest ancestral path between any vertex in v and any vertex in w; -1 if no such path
    public int length(Iterable<Integer> v, Iterable<Integer> w) {
        validate(v, w);
        return deluxeBfs(v, w)[1];
    }

    // a common ancestor that participates in shortest ancestral path; -1 if no such path
    public int ancestor(Iterable<Integer> v, Iterable<Integer> w) {
        validate(v, w);
        return deluxeBfs(v, w)[0];
    }

    private int[] deluxeBfs(Iterable<Integer> v, Iterable<Integer> w) {
        int ancestor = -1;
        int path = Integer.MAX_VALUE;
        int[] res = {ancestor, path};

        // do v and w have a common vertex?
        ArrayList<Integer> vIterable = new ArrayList<>();
        v.forEach(vIterable::add);
        ArrayList<Integer> wIterable = new ArrayList<>();
        w.forEach(wIterable::add);


        for (int i : vIterable) {
            if (wIterable.contains(i)) { // short circuit
                res[0] = i;
                res[1] = 0;
                return res;
            }
        }

        Queue<Integer> vQ = new Queue<>(); // queue from v
        Queue<Integer> wQ = new Queue<>(); // queue from w
        boolean[] vMarked = new boolean[range];
        boolean[] wMarked = new boolean[range];
        int[] distFromV = new int[range];
        int[] distFromW = new int[range];

        // enqueue all the v-set vertices
        for (int s : v) {
            vMarked[s] = true;
            distFromV[s] = 0;
            vQ.enqueue(s);
        }
        // enqueue all the w-set vertices
        for (int s : w) {
            wMarked[s] = true;
            distFromW[s] = 0;
            wQ.enqueue(s);
        }

/*SAP.java:109: Avoid quadruple nested 'if' statements; they are hard to read and error-prone to maintain. [AvoidDeeplyNestedIfStmts]
SAP.java:125: Avoid quadruple nested 'if' statements; they are hard to read and error-prone to maintain. [AvoidDeeplyNestedIfStmts]*/

        //bfs in lockstep
        while (!vQ.isEmpty() || !wQ.isEmpty()) {
            if (!vQ.isEmpty()) {
                int v1 = vQ.dequeue();
                for (int v2 : G.adj(v1)) {
                    if (!vMarked[v2]) {
                        vMarked[v2] = true;
                        vQ.enqueue(v2);
                        distFromV[v2] = distFromV[v1] + 1;
                        if (wMarked[v2]) {// we have a path
                            int distV2 = distFromV[v2] + distFromW[v2];
                            if (distV2 >= res[1]) continue; // no shorter path from this vertex
                            res[0] = v2;
                            res[1] = distV2;
                        }
                    }
                }
            }
            if (!wQ.isEmpty()) {
                int w1 = wQ.dequeue();
                for (int w2 : G.adj(w1)) {
                    if (!wMarked[w2]) {
                        wMarked[w2] = true;
                        wQ.enqueue(w2);
                        distFromW[w2] = distFromW[w1] + 1;
                        if (vMarked[w2]) {
                            int distW2 = distFromV[w2] + distFromW[w2];
                            if (distW2 >= res[1]) continue;
                            res[0] = w2;
                            res[1] = distW2;
                        }
                    }
                }
            }
        }
        if (res[1] == Integer.MAX_VALUE) {
            return new int[]{-1, -1};
        }
        return res;
    }

    private void validate(Object v) {
        if (null == v) throw new IllegalArgumentException();
        if ((int) v < 0 || (int) v >= range) throw new IllegalArgumentException();
    }

    private void validate(Iterable<Integer> v, Iterable<Integer> w) {
        try {
            for (Object i : v) {
                validate(i);
            }
            for (Object j : w) {
                validate(j);
            }
        } catch (NullPointerException e)  {
            throw new IllegalArgumentException();
        }
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        Digraph G = new Digraph(in);
        SAP sap = new SAP(G);
        // while (!StdIn.isEmpty()) {
/*        int v = 12; //StdIn.readInt();
        int w = 13; //StdIn.readInt();*/
        ArrayList<Integer> v = null;
        //= new ArrayList<>();
        //{ 0, 7, 9, 12 }
        /*v.add(0);
        v.add(7);
        v.add(9);
        v.add(12);
       */ //v.add(10);

        ArrayList<Integer> w = null;
        /*= new ArrayList<>();
        w.add(null);
      */  /*w.add(10);
        w.add(12);*/


        int ancestor = sap.ancestor(v, w);
        StdOut.printf("ancestor = %d\n", ancestor);
        int length = sap.length(v, w);
        StdOut.printf("length = %d\n", length);
    }
}