From https://algs4.cs.princeton.edu/42digraph/
- Reachable vertex in a digraph. Design a linear-time algorithm to determine whether a digraph has a vertex that is reachable from every other vertex.
Kosaraju-Sharir algorithm gives us the strongly connected components. Java code for that can be seen here. Reducing each SCC to a single vertex, a vertex that has outdegree zero is reachable from every other.
Problem is, everyone seems to be talking about reducing a SCC without providing details. What is an efficient algorithm to do so?
Following is a Java solution to my own question. For the graph representation, it uses edu.princeton.cs:algs4:1.0.3
from https://github.com/kevin-wayne/algs4. There appears to be general algorithms for graph contraction, as outlined in this paper; however, for my purposes, the following is sufficient.
/**
* 43. <b>Reachable vertex.</b>
* <p>
* DAG: Design a linear-time algorithm to determine whether a DAG has a vertex that is reachable from every other
* vertex, and if so, find one.
* Digraph: Design a linear-time algorithm to determine whether a digraph has a vertex that is reachable from every
* other vertex, and if so, find one.
* <p>
* Answer:
* DAG: Consider an edge (u, v) ∈ E. Since the graph is acyclic, u is not reachable from v.
* Thus u cannot be the solution to the problem. From this it follows that only a vertex of
* outdegree zero can be a solution. Furthermore, there has to be exactly one vertex with outdegree zero,
* or the problem has no solution. This is because if there were multiple vertices with outdegree zero,
* they wouldn't be reachable from each other.
* <p>
* Digraph: Reduce the graph to it's Kernel DAG, then find a vertex of outdegree zero.
*/
public class Scc {
private final Digraph g;
private final Stack<Integer> s = new Stack<>();
private final boolean marked[];
private final Digraph r;
private final int[] scc;
private final Digraph kernelDag;
public Scc(Digraph g) {
this.g = g;
this.r = g.reverse();
marked = new boolean[g.V()];
scc = new int[g.V()];
Arrays.fill(scc, -1);
for (int v = 0; v < r.V(); v++) {
if (!marked[v]) visit(v);
}
int i = 0;
while (!s.isEmpty()) {
int v = s.pop();
if (scc[v] == -1) visit(v, i++);
}
Set<Integer> vPrime = new HashSet<>();
Set<Map.Entry<Integer, Integer>> ePrime = new HashSet<>();
for (int v = 0; v < scc.length; v++) {
vPrime.add(scc[v]);
for (int w : g.adj(v)) {
// no self-loops, no parallel edges
if (scc[v] != scc[w]) {
ePrime.add(new SimpleImmutableEntry<>(scc[v], scc[w]));
}
}
}
kernelDag = new Digraph(vPrime.size());
for (Map.Entry<Integer, Integer> e : ePrime) kernelDag.addEdge(e.getKey(), e.getValue());
}
public int reachableFromAllOther() {
for (int v = 0; v < kernelDag.V(); v++) {
if (kernelDag.outdegree(v) == 0) return v;
}
return -1;
}
// reverse postorder
private void visit(int v) {
marked[v] = true;
for (int w : r.adj(v)) {
if (!marked[w]) visit(w);
}
s.push(v);
}
private void visit(int v, int i) {
scc[v] = i;
for (int w : g.adj(v)) {
if (scc[w] == -1) visit(w, i);
}
}
}
Running it on the graph below produces the strongly-connected components as shown. Vertex 0 in the reduced DAG is reachable from every other vertex.
What I couldn't find anywhere is the kind of detail that I presented above. Comments like "well, this is easy, you do that, then you do something else" are thrown around without concrete details.