1 files changed, 65 insertions, 0 deletions
diff --git a/Algorithms/Part-II/1-WordNet/SAP.java b/Algorithms/Part-II/1-WordNet/SAP.java
new file mode 100644
index 0000000..864b8d0
--- /dev/null
+++ b/Algorithms/Part-II/1-WordNet/SAP.java
@@ -0,0 +1,65 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+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
+
+    // constructor takes a digraph (not necessarily a DAG)
+    public SAP(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;
+    }
+
+    // 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;
+    }
+
+    // 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;
+    }
+
+    // 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 -1;
+    }
+
+    // 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);
+        }
+    }
+}
+