summaryrefslogtreecommitdiffstats
path: root/Algorithms/Part-II
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms/Part-II')
-rw-r--r--Algorithms/Part-II/1-WordNet/Outcast.java20
-rw-r--r--Algorithms/Part-II/1-WordNet/SAP.java232
-rw-r--r--Algorithms/Part-II/1-WordNet/SpecializedBFS.java150
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");
- }
-}
generated by cgit v1.1-2-g2b99 at 2024-11-26 03:55:23 +0100