package graphs.digraphs;

/**
 *  Determine single-source or multiple-source reachability in a digraph
 *  using depth first search.
 */
public class DiGraphDFSearch {
	private boolean[] visited;  

	// single-source reachability
	public DiGraphDFSearch(DiGraph G, int s) {
		visited = new boolean[G.numberOfVerteces()];
		dfs(G, s);
	}

	// multiple-source reachability
	public DiGraphDFSearch(DiGraph G, Iterable<Integer> sources) {
		visited = new boolean[G.numberOfVerteces()];
		for (int v : sources)
			dfs(G, v);
	}

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

	// is there a directed path from the source (or sources) to v?
	public boolean visited(int v) {
		return visited[v];
	}

}