001package algs42;
002import stdlib.*;
003import algs13.Stack;
004/* ***********************************************************************
005 *  Compilation:  javac DepthFirstDirectedPaths.java
006 *  Execution:    java DepthFirstDirectedPaths G s
007 *  Dependencies: Digraph.java Stack.java
008 *
009 *  Determine reachability in a digraph from a given vertex using
010 *  depth first search.
011 *  Runs in O(E + V) time.
012 *
013 *  % tinyDG.txt 3
014 *  3 to 0:  3-5-4-2-0
015 *  3 to 1:  3-5-4-2-0-1
016 *  3 to 2:  3-5-4-2
017 *  3 to 3:  3
018 *  3 to 4:  3-5-4
019 *  3 to 5:  3-5
020 *  3 to 6:  not connected
021 *  3 to 7:  not connected
022 *  3 to 8:  not connected
023 *  3 to 9:  not connected
024 *  3 to 10:  not connected
025 *  3 to 11:  not connected
026 *  3 to 12:  not connected
027 *
028 *************************************************************************/
029
030public class DepthFirstDirectedPaths {
031        private final boolean[] marked;  // marked[v] = true if v is reachable from s
032        private final int[] edgeTo;      // edgeTo[v] = last edge on path from s to v
033        private final int s;       // source vertex
034
035        // single source
036        public DepthFirstDirectedPaths(Digraph G, int s) {
037                marked = new boolean[G.V()];
038                edgeTo = new int[G.V()];
039                this.s = s;
040                dfs(G, s);
041        }
042
043
044        private void dfs(Digraph G, int v) {
045                marked[v] = true;
046                for (int w : G.adj(v)) {
047                        if (!marked[w]) {
048                                edgeTo[w] = v;
049                                dfs(G, w);
050                        }
051                }
052        }
053
054        // is there a directed path from s to v?
055        public boolean hasPathTo(int v) {
056                return marked[v];
057        }
058
059        // return path from s to v; null if no such path
060        public Iterable<Integer> pathTo(int v) {
061                if (!hasPathTo(v)) return null;
062                Stack<Integer> path = new Stack<>();
063                for (int x = v; x != s; x = edgeTo[x])
064                        path.push(x);
065                path.push(s);
066                return path;
067        }
068
069        public static void main(String[] args) {
070                args = new String[] { "data/tinyDG.txt", "3" };
071
072                In in = new In(args[0]);
073                Digraph G = DigraphGenerator.fromIn(in);
074                // StdOut.println(G);
075
076                int s = Integer.parseInt(args[1]);
077                DepthFirstDirectedPaths dfs = new DepthFirstDirectedPaths(G, s);
078
079                for (int v = 0; v < G.V(); v++) {
080                        if (dfs.hasPathTo(v)) {
081                                StdOut.format("%d to %d:  ", s, v);
082                                for (int x : dfs.pathTo(v)) {
083                                        if (x == s) StdOut.print(x);
084                                        else        StdOut.print("-" + x);
085                                }
086                                StdOut.println();
087                        }
088
089                        else {
090                                StdOut.format("%d to %d:  not connected\n", s, v);
091                        }
092
093                }
094        }
095
096}