diff options
Diffstat (limited to 'Algorithms/Part-II/1-WordNet/SAP.java')
| -rw-r--r-- | Algorithms/Part-II/1-WordNet/SAP.java | 232 |
1 files changed, 166 insertions, 66 deletions
diff --git a/Algorithms/Part-II/1-WordNet/SAP.java b/Algorithms/Part-II/1-WordNet/SAP.java index 264102a..39c6df3 100644 --- a/Algorithms/Part-II/1-WordNet/SAP.java +++ b/Algorithms/Part-II/1-WordNet/SAP.java @@ -1,131 +1,231 @@ /* vim: set expandtab tabstop=4 shiftwidth=4 : */ +import java.util.Iterator; + public class SAP { - // data type use space proportional to E + V - // all methods take time at most proportional to E + V in the worst case - private static class SAPResult { - private int ancestor; - private int length; - public SAPResult(int a, int l) { - ancestor = a; - length = l; + private final Digraph g; + private final BFS vBFS; + private final BFS wBFS; + + private class BFS implements Iterable<Integer> + { + private static final int MAXINT = Integer.MAX_VALUE; + + private boolean[] marked; + private int[] distTo; + private Queue<Integer> visited; + private Queue<Integer> q; + + public BFS(int size) + { + marked = new boolean[size]; + distTo = new int[size]; + visited = new Queue<Integer>(); + q = new Queue<Integer>(); + for (int v = 0; v < size; v++) { + // distTo[v] = -1; + marked[v] = false; + } + } + + public void bfs(int s) + { + clear(); + + marked[s] = true; + distTo[s] = 0; + + q.enqueue(s); + visited.enqueue(s); + bfs(); } - public int length() { return length; } - public int ancestor() { return ancestor; } - }; - private Digraph g; + public void bfs(Iterable<Integer> ss) + { + clear(); + + for (int s : ss) { + marked[s] = true; + distTo[s] = 0; + q.enqueue(s); + visited.enqueue(s); + } + + bfs(); + } + + public int distTo(int v) + { + return distTo[v]; + } + + public boolean hasPathTo(int v) + { + return marked[v]; + } + + public Iterator<Integer> iterator() { + return visited.iterator(); + } + + public int visitedCount() + { + return visited.size(); + } + + private void clear() + { + while (!visited.isEmpty()) { + marked[visited.dequeue()] = false; + } + } + + private void bfs() + { + while (!q.isEmpty()) { + int v = q.dequeue(); + for (int w : g.adj(v)) { + if (!marked[w]) { + distTo[w] = distTo[v] + 1; + marked[w] = true; + q.enqueue(w); + visited.enqueue(w); + } + } + } + } + } + + // data type use space proportional to E + V + // all methods take time at most proportional to E + V in the worst case // constructor takes a digraph (not necessarily a DAG) public SAP(Digraph G) { g = new Digraph(G); + vBFS = new BFS(G.V()); + wBFS = new BFS(G.V()); } // length of shortest ancestral path between v and w // -1 if no such path public int length(int v, int w) { - return ancestorAndLength(v, w).length(); + check(v); + check(w); + + vBFS.bfs(v); + wBFS.bfs(w); + + return distance(); } // 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) { - return ancestorAndLength(v, w).ancestor(); + check(v); + check(w); + + vBFS.bfs(v); + wBFS.bfs(w); + + return ancestor(); } // 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) { - return ancestorAndLength(v, w).length(); + check(v); + check(w); + + vBFS.bfs(v); + wBFS.bfs(w); + + return distance(); } // a common ancestor that participates in shortest ancestral path // -1 if no such path public int ancestor(Iterable<Integer> v, Iterable<Integer> w) { - return ancestorAndLength(v, w).ancestor(); + check(v); + check(w); + + vBFS.bfs(v); + wBFS.bfs(w); + + return ancestor(); } - private SAPResult ancestorAndLength(int v, int w) + private int distance() { - if ((Math.max(v, w) >= g.V()) || (Math.min(v, w) < 0)) - throw new IndexOutOfBoundsException("out of index"); - - // the smallest index shall have the smallest components count - int a, b; - if (v < w) { - a = v; - b = w; + BFS aBFS, bBFS; + if (vBFS.visitedCount() < wBFS.visitedCount()) { + aBFS = vBFS; + bBFS = wBFS; } else { - a = w; - b = v; + aBFS = wBFS; + bBFS = vBFS; } - int sol = -1; int len = Integer.MAX_VALUE; - if (a == b) { - sol = a; - len = 0; - } else { - - ResizingArrayQueue<Integer> c = new ResizingArrayQueue<Integer>(); - SpecializedBFS aBFS = new SpecializedBFS(g, a, c); - SpecializedBFS bBFS = new SpecializedBFS(g, b, null); - - for (int x : c) { - if (!bBFS.hasPathTo(x)) continue; + for (int x : aBFS) { + if (bBFS.hasPathTo(x)) { int l = aBFS.distTo(x) + bBFS.distTo(x); - if (len > l) { + if (l < len) { len = l; - sol = x; } } } - if (sol == -1) len = -1; - - return new SAPResult(sol, len); + if (len == Integer.MAX_VALUE) + return -1; + return len; } - private SAPResult ancestorAndLength(Iterable<Integer> vv, Iterable<Integer> ww) + private int ancestor() { - for (int v : vv) { - if (v < 0 || v >= g.V()) - throw new IndexOutOfBoundsException("out of index"); - } - for (int w : ww) { - if (w < 0 || w >= g.V()) - throw new IndexOutOfBoundsException("out of index"); + BFS aBFS, bBFS; + if (vBFS.visitedCount() < wBFS.visitedCount()) { + aBFS = vBFS; + bBFS = wBFS; + } else { + aBFS = wBFS; + bBFS = vBFS; } - int sol = -1; + int ancestor = -1; int len = Integer.MAX_VALUE; - ResizingArrayQueue<Integer> c = new ResizingArrayQueue<Integer>(); - SpecializedBFS aBFS = new SpecializedBFS(g, vv, c); - SpecializedBFS bBFS = new SpecializedBFS(g, ww, null); - - for (int x : c) { - if (!bBFS.hasPathTo(x)) continue; - int l = aBFS.distTo(x) + bBFS.distTo(x); - if (len > l) { - len = l; - sol = x; + for (int x : aBFS) { + if (bBFS.hasPathTo(x)) { + int l = aBFS.distTo(x) + bBFS.distTo(x); + if (l < len) { + len = l; + ancestor = x; + } } } - if (sol == -1) len = -1; + return ancestor; + } - SAPResult res = new SAPResult(sol, len); + private void check(int v) + { + if (v < 0 || v >= g.V()) + throw new IndexOutOfBoundsException("out of index"); + } - return res; + private void check(Iterable<Integer> vs) + { + for (int v : vs) { + check(v); + } } // for unit testing of this class (such as the one below) |