001package algs42;
002import stdlib.*;
003import algs13.Bag;
004/* ***********************************************************************
005 *  Compilation:  javac DirectedDFS.java
006 *  Execution:    java DirectedDFS V E
007 *  Dependencies: Digraph.java Bag.java In.java StdOut.java
008 *  Data files:   http://www.cs.princeton.edu/algs4/42directed/tinyDG.txt
009 *
010 *  Determine single-source or multiple-source reachability in a digraph
011 *  using depth first search.
012 *  Runs in O(E + V) time.
013 *
014 *  % java DirectedDFS tinyDG.txt 1
015 *  1
016 *
017 *  % java DirectedDFS tinyDG.txt 2
018 *  0 1 2 3 4 5
019 *
020 *  % java DirectedDFS tinyDG.txt 1 2 6
021 *  0 1 2 3 4 5 6 9 10 11 12
022 *
023 *************************************************************************/
024
025public class DirectedDFS {
026        private final boolean[] marked;  // marked[v] = true if v is reachable
027        // from source (or sources)
028
029        // single-source reachability
030        public DirectedDFS(Digraph G, int s) {
031                marked = new boolean[G.V()];
032                dfs(G, s);
033        }
034
035        // multiple-source reachability
036        public DirectedDFS(Digraph G, Iterable<Integer> sources) {
037                marked = new boolean[G.V()];
038                for (int v : sources)
039                        dfs(G, v);
040        }
041
042        private void dfs(Digraph G, int v) {
043                marked[v] = true;
044                for (int w : G.adj(v)) {
045                        if (!marked[w]) dfs(G, w);
046                }
047        }
048
049        // is there a directed path from the source (or sources) to v?
050        public boolean marked(int v) {
051                return marked[v];
052        }
053
054        // test client
055        public static void main(String[] args) {
056                //args = new String[] { "data/tinyDG.txt", "1" };
057                args = new String[] { "data/tinyDG.txt", "2" };
058                //args = new String[] { "data/tinyDG.txt", "1", "2", "6" };
059
060                // read in digraph from command-line argument
061                In in = new In(args[0]);
062                Digraph G = DigraphGenerator.fromIn(in);
063
064                // read in sources from command-line arguments
065                Bag<Integer> sources = new Bag<>();
066                for (int i = 1; i < args.length; i++) {
067                        int s = Integer.parseInt(args[i]);
068                        sources.add(s);
069                }
070
071                // multiple-source reachability
072                DirectedDFS dfs = new DirectedDFS(G, sources);
073
074                // print out vertices reachable from sources
075                for (int v = 0; v < G.V(); v++) {
076                        if (dfs.marked(v)) StdOut.print(v + " ");
077                }
078                StdOut.println();
079        }
080
081}