2

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?

5
  • 1
    Well, you basically have to construct a new graph when k vertexes (k being the number of SCCs) and m edges: each "old" edge becomes a "new" edge between corresponding SCCs. I'm not sure what is the source of confusion — the algorithm itself, its correctness, its running time, implementation details?
    – yeputons
    Jun 24, 2018 at 11:24
  • 1
    @yeputons the source of the confusion is the lack of detail regarding “how”. What you said doesn’t add anything more to what I already know. Jun 24, 2018 at 17:30
  • You use any algorithm to determine SCCs. After that you know which vertex belongs to which SCC, that is you have a list of sets of vertices. Then you create a new graph, add one vertex for each SCC (which is a set of vertices). Then you iterate every vertex per SCC and add the edges. Therefore you need to know the mapping in the other direction (vertex to its SCC). Usually people use what is called Union-Find (Wikipedia) for all of this. The approach should be crystal clear. Please provide more details on the exact issues.
    – Zabuzard
    Jun 24, 2018 at 21:35
  • @Zabuza already posted a solution myself, you're little late. Thanks. Jun 24, 2018 at 21:36
  • @AbhijitSarkar Yes, I see that. Looks fairly complicated to be honest. I did this task in three projects already. It's a lot easier if you setup your SCC class better. That is, it should represent a Set<Vertex> and you should have some Map<Vertex, SCC> (or a Union-Find data-structure). Then it's just 10 lines of code.
    – Zabuzard
    Jun 24, 2018 at 21:40

2 Answers 2

2

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.

1

Suppose you already have a method to compute SCCs and the usual graph, vertex and edge methods. Then it's just creating a new graph, adding a vertex representative for each SCC and then adding edge representatives.

For the edges you need to be able to map an original vertex (the edge destination) to its representative in the new graph. You can model that in the first pass using a Map<Vertex, SCC> which maps vertices to their SCCs and a Map<SCC, Vertex> which maps SCCs to their representative vertices in the new graph. Or you directly have a Map<Vertex, Vertex> mapping original vertices to their representatives.


Here is a Java solution:

public static Graph graphToSccGraph(Graph graph) {
    Collection<SCC> sccs = SccComputation.computeSccs(graph);
    Graph sccGraph = new Graph();

    Map<Vertex, SCC> vertexToScc = new HashMap<>();
    Map<SCC, Vertex> sccToRep = new HashMap<>();

    // Add a representative for each SCC (O(|V|))
    for (SCC scc : sccs) {
        Vertex rep = new Vertex();
        sccGraph.addVertex(rep);

        sccToRep.put(scc, rep);
        for (Vertex vertex : scc.getVertices()) {
            vertexToScc.put(vertex, scc);
        }
    }

    // Add edge representatives (O(|E|))
    for (Vertex vertex : graph.getVertices()) {
        Vertex sourceRep = sccToRep.get(vertexToScc.get(vertex));
        for (Edge edge : vertex.getOutgoingEdges()) {
           Vertex destRep = sccToRep.get(vertexToScc.get(edge.getDestination()));
           Edge edgeRep = new Edge(sourceRep, destRep);
              if (!sccGraph.contains(edgeRep)) {
                  sccGraph.addEdge(edgeRep);
              }
        }
    }

    return sccGraph;
}

Time complexity is linear in the size of the graph (amount of vertices and edges), so optimal. That is Theta(|V| + |E|).

Usually people use a Union-Find (see Wikipedia) data-structure to make this even simpler and get rid of the Maps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.