Algorithms-II : 1-WordNet: implementation

1 files changed, 133 insertions, 21 deletions

diff --git a/Algorithms/Part-II/1-WordNet/SAP.java b/Algorithms/Part-II/1-WordNet/SAP.java
index 864b8d0..264102a 100644
--- a/Algorithms/Part-II/1-WordNet/SAP.java
+++ b/Algorithms/Part-II/1-WordNet/SAP.java
@@ -3,63 +3,175 @@
 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;
+        }
+        public int length() { return length; }
+        public int ancestor() { return ancestor; }
+    };
+
+    private Digraph g;
+
     // constructor takes a digraph (not necessarily a DAG)
     public SAP(Digraph G)
     {
+        g = new Digraph(G);
     }
 
     // length of shortest ancestral path between v and w
     // -1 if no such path
     public int length(int v, int w)
     {
-        // throws java.lang.IndexOutOfBoundsException if args not in [0 ; G.V()-1]
-
-        return -1;
+        return ancestorAndLength(v, w).length();
     }
 
     // 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)
     {
-        // throws java.lang.IndexOutOfBoundsException if args not in [0 ; G.V()-1]
-
-        return -1;
+        return ancestorAndLength(v, w).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)
     {
-        // throws java.lang.IndexOutOfBoundsException if args not in [0 ; G.V()-1]
-
-        return -1;
+        return ancestorAndLength(v, w).length();
     }
 
     // a common ancestor that participates in shortest ancestral path
     // -1 if no such path
     public int ancestor(Iterable<Integer> v, Iterable<Integer> w)
     {
-        // throws java.lang.IndexOutOfBoundsException if args not in [0 ; G.V()-1]
+        return ancestorAndLength(v, w).ancestor();
+    }
+
+    private SAPResult ancestorAndLength(int v, int w)
+    {
+        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;
+        } else {
+            a = w;
+            b = v;
+        }
+
+        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;
+                int l = aBFS.distTo(x) + bBFS.distTo(x);
+                if (len > l) {
+                    len = l;
+                    sol = x;
+                }
+            }
+        }
+
+        if (sol == -1) len = -1;
+
+        return new SAPResult(sol, len);
+    }
+
+    private SAPResult ancestorAndLength(Iterable<Integer> vv, Iterable<Integer> ww)
+    {
+        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");
+        }
+
+        int sol = -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;
+            }
+        }
+
+        if (sol == -1) len = -1;
+
+        SAPResult res = new SAPResult(sol, len);
 
-        return -1;
+        return res;
     }
 
     // for unit testing of this class (such as the one below)
     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 = StdIn.readInt();
-            int w = StdIn.readInt();
-            int length   = sap.length(v, w);
-            int ancestor = sap.ancestor(v, w);
-            StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
+        int length, ancestor;
+        In in;
+        Digraph G;
+        SAP sap;
+
+        in = new In("./data/digraph1.txt");
+        G = new Digraph(in);
+        sap = new SAP(G);
+
+        length = sap.length(3, 11);
+        ancestor = sap.ancestor(3, 11);
+        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
+
+        length = sap.length(9, 12);
+        ancestor = sap.ancestor(9, 12);
+        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
+
+        length = sap.length(7, 2);
+        ancestor = sap.ancestor(7, 2);
+        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
+
+        length = sap.length(1, 6);
+        ancestor = sap.ancestor(1, 6);
+        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
+
+        Stopwatch w1 = new Stopwatch();
+        for (int i = 1; i < 7; i++) {
+            String g = "./data/digraph"+i+".txt";
+            in = new In(g);
+            G = new Digraph(in);
+            sap = new SAP(G);
+            for (int v = 0; v < G.V(); v++) {
+                for (int w = 0; w < G.V(); w++) {
+                    int a = sap.ancestor(v, w);
+                    int l = sap.length(v, w);
+                    // StdOut.printf("%s %d->%d : a:%d l:%d\n", g, v, w, a, l);
+                }
+            }
         }
+        double a1 = w1.elapsedTime();
+        StdOut.printf("all solved in : %g \n", a1);
     }
 }