package graphs.digraphs;
import java.util.Stack;

/**
 *  Determine reachability in a digraph from a given vertex using
 *  depth first search.
 */
public class DiGraphDFSPath {
	private boolean[] visited;  // visited[v] = true if v is reachable from s
    private int[] edgeTo;      // edgeTo[v] = last edge on path from s to v
    private final int s;       // source vertex

    public DiGraphDFSPath(DiGraph G, int s) {
        visited = new boolean[G.numberOfVerteces()];
        edgeTo = new int[G.numberOfVerteces()];
        this.s = s;
        dfs(G, s);
    }

    private void dfs(DiGraph G, int v) { 
        visited[v] = true;
        for (int w : G.adjacents(v)) {
            if (!visited[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    // is there a directed path from s to v?
    public boolean hasPathTo(int v) {
        return visited[v];
    }

    // return path from s to v; null if no such path
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> stack = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x])
            stack.push(x);
        stack.push(s);
        return stack;
    }

}