Algorithms-II : 1-WordNet: speedup using BFS with visited Queue, cleared before bfs()

3 files changed, 183 insertions, 219 deletions

diff --git a/Algorithms/Part-II/1-WordNet/Outcast.java b/Algorithms/Part-II/1-WordNet/Outcast.java
index af2b6f3..e9d7911 100644
--- a/Algorithms/Part-II/1-WordNet/Outcast.java
+++ b/Algorithms/Part-II/1-WordNet/Outcast.java
@@ -38,14 +38,28 @@ public class Outcast
         Outcast outcast = new Outcast(wordnet);
         String[] nouns;
 
+        Stopwatch st = new Stopwatch();
+        double t0, t1 = 0;
+
         nouns = new In("./data/outcast5.txt").readAllStrings();
-        StdOut.println(outcast.outcast(nouns));
+        t0 = st.elapsedTime();
+        StdOut.println(outcast.outcast(nouns)+" " + (t0 - t1));
+        t1 = t0;
 
         nouns = new In("./data/outcast8.txt").readAllStrings();
-        StdOut.println(outcast.outcast(nouns));
+        t0 = st.elapsedTime();
+        StdOut.println(outcast.outcast(nouns)+" " + (t0 - t1));
+        t1 = t0;
 
         nouns = new In("./data/outcast11.txt").readAllStrings();
-        StdOut.println(outcast.outcast(nouns));
+        t0 = st.elapsedTime();
+        StdOut.println(outcast.outcast(nouns)+" " + (t0 - t1));
+        t1 = t0;
+
+        nouns = new In("./data/outcast29.txt").readAllStrings();
+        t0 = st.elapsedTime();
+        StdOut.println(outcast.outcast(nouns)+" " + (t0 - t1));
+        t1 = t0;
     }
 }
 
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)
diff --git a/Algorithms/Part-II/1-WordNet/SpecializedBFS.java b/Algorithms/Part-II/1-WordNet/SpecializedBFS.java
deleted file mode 100644
index 5b4a635..0000000
--- a/Algorithms/Part-II/1-WordNet/SpecializedBFS.java
+++ /dev/null
@@ -1,150 +0,0 @@
-/* vim: set expandtab tabstop=4 shiftwidth=4 : */
-
-public class SpecializedBFS
-{
-    private static final int MAXINT = Integer.MAX_VALUE;
-
-    private boolean[] marked;
-    private int[] edgeTo;
-    private int[] distTo;
-
-    public SpecializedBFS(Digraph G, int s, ResizingArrayQueue<Integer> c)
-    {
-        init(G);
-        Queue<Integer> q = new Queue<Integer>();
-        marked[s] = true;
-        distTo[s] = 0;
-        q.enqueue(s);
-        if (c != null) c.enqueue(s);
-        bfs(G, q, c);
-    }
-
-    public SpecializedBFS(Digraph G, Iterable<Integer> ss,
-            ResizingArrayQueue<Integer> c)
-    {
-        init(G);
-        Queue<Integer> q = new Queue<Integer>();
-        for (int s : ss) {
-            marked[s] = true;
-            distTo[s] = 0;
-            q.enqueue(s);
-            if (c != null) c.enqueue(s);
-        }
-        bfs(G, q, c);
-    }
-
-    private void init(Digraph g)
-    {
-        marked = new boolean[g.V()];
-        edgeTo = new int[g.V()];
-        distTo = new int[g.V()];
-        for (int v = 0; v < g.V(); v++)
-            distTo[v] = MAXINT;
-    }
-
-    public int distTo(int v)
-    {
-        return distTo[v];
-    }
-
-    public boolean hasPathTo(int v)
-    {
-        return marked[v];
-    }
-
-    private void bfs(Digraph G, Queue<Integer> q, ResizingArrayQueue<Integer> c)
-    {
-        while (!q.isEmpty()) {
-            int v = q.dequeue();
-            for (int w : G.adj(v)) {
-                if (!marked[w]) {
-                    edgeTo[w] = v;
-                    distTo[w] = distTo[v] + 1;
-                    marked[w] = true;
-                    q.enqueue(w);
-                    if (c != null) c.enqueue(w);
-                }
-            }
-        }
-    }
-
-    // change this to an iterator if efficiency is needed
-    public Iterable<Integer> pathTo(int v)
-    {
-        if (!hasPathTo(v)) return null;
-
-        Stack<Integer> path = new Stack<Integer>();
-        int x;
-        for (x = v; distTo[x] != 0; x = edgeTo[x])
-            path.push(x);
-        path.push(x);
-
-        return path;
-    }
-
-    public int pathToCount(int v)
-    {
-        if (!hasPathTo(v)) return MAXINT;
-
-        int count = 0;
-        for (int x = v; distTo[x] != 0; x = edgeTo[x])
-            count++;
-
-        return count;
-    }
-
-    public static void main(String[] args)
-    {
-        In in = new In("./data/digraph3.txt");
-        Digraph G = new Digraph(in);
-        StdOut.println(G);
-
-        int s = 7;
-        ResizingArrayQueue<Integer> components = new ResizingArrayQueue<Integer>();
-        SpecializedBFS bfs = new SpecializedBFS(G, s, components);
-
-        for (int v = 0; v < G.V(); v++) {
-            if (bfs.hasPathTo(v)) {
-                StdOut.printf("%2d -> %2d: [%d]  ", s, v, bfs.distTo(v));
-                for (int x : bfs.pathTo(v)) {
-                    if (x == s) StdOut.print(x);
-                    else        StdOut.print("->" + x);
-                }
-                StdOut.println();
-            } else {
-                StdOut.printf("%2d -> %2d: [-]\n", s, v);
-            }
-        }
-        StdOut.printf("components : ");
-        for (int c : components) {
-            if (c == s) StdOut.print(c);
-            else        StdOut.print("->" + c);
-        }
-        StdOut.print("\n");
-        StdOut.printf("pathToCount(%d) : %2d\n", 4, bfs.pathToCount(4));
-        StdOut.printf("pathToCount(%d) : %2d\n", 9, bfs.pathToCount(9));
-
-        int s2 = 11;
-        SpecializedBFS bfs2 = new SpecializedBFS(G, s2, null);
-
-        for (int v = 0; v < G.V(); v++) {
-            if (bfs2.hasPathTo(v)) {
-                StdOut.printf("%2d -> %2d: [%d]  ", s2, v, bfs2.distTo(v));
-                for (int x : bfs2.pathTo(v)) {
-                    if (x == s2) StdOut.print(x);
-                    else        StdOut.print("->" + x);
-                }
-                StdOut.println();
-            } else {
-                StdOut.printf("%2d -> %2d: [-]\n", s2, v);
-            }
-        }
-
-        StdOut.printf("intersection : ");
-        for (int c : components) {
-            if (bfs2.hasPathTo(c))
-                    StdOut.print(c+" ");
-        }
-        StdOut.print("\n");
-    }
-}