1 files changed, 150 insertions, 0 deletions
diff --git a/Algorithms/Part-II/1-WordNet/SpecializedBFS.java b/Algorithms/Part-II/1-WordNet/SpecializedBFS.java
new file mode 100644
index 0000000..5b4a635
--- /dev/null
+++ b/Algorithms/Part-II/1-WordNet/SpecializedBFS.java
@@ -0,0 +1,150 @@
+/* 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");
+    }
+}