algorithmgraphdirected-graphstrongly-connected-graph

How to reduce a strongly connected component to one vertex?


From https://algs4.cs.princeton.edu/42digraph/

  1. 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?


Solution

  • 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. enter image description here

    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.