diff options
Diffstat (limited to 'Algorithms/Part-II/1-WordNet/SAP.java')
| -rw-r--r-- | Algorithms/Part-II/1-WordNet/SAP.java | 154 |
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); } } |