Как свести сильно связанный компонент к одной вершине?

Question

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

43. Достижимая вершина в орграфе. Разработка алгоритма с линейным временем, чтобы определить, есть ли у орграфа вершина, достижимая из каждая вторая вершина.

Алгоритм Косараю-Шарира дает нам сильно связанные компоненты. Код Java для этого можно увидеть здесь . Сведение каждого SCC к одной вершине, вершина с нулевым градусом достижима из любой другой.

Проблема в том, что все, кажется, говорят о сокращении SCC без предоставления подробностей. Что такое эффективный алгоритм для этого?

Answer 1

Предположим, у вас уже есть метод для вычисления SCC s и обычные методы графа, вершины и ребра.Затем это просто создание нового графа, добавление представителя вершины для каждого SCC, а затем добавление представителей ребер.

Для ребер необходимо иметь возможность сопоставить исходную вершину (назначение ребер) с ее представителем вновый график.Вы можете смоделировать это в первом проходе, используя Map<Vertex, SCC>, который отображает вершины в их SCC, и Map<SCC, Vertex>, который отображает SCC в их репрезентативные вершины в новом графе.Или у вас есть Map<Vertex, Vertex> отображение исходных вершин на их представителей.

---

Вот решение Java:

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;
}

---

Сложность времени линейная в размере графа (количество вершин и ребер), поэтому оптимально .Это Theta(|V| + |E|).

Обычно люди используют структуру данных Union-Find (см. Wikipedia ), чтобы сделать это еще проще и избавиться от Map s.

Answer 2

Ниже приведено решение Java для моего собственного вопроса.Для представления графа он использует edu.princeton.cs:algs4:1.0.3 из https://github.com/kevin-wayne/algs4. Похоже, что существуют общие алгоритмы сжатия графа, описанные в этой статье ;однако для моих целей достаточно следующего:

/**
 * 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);
        }
    }
}

Запуск его на приведенном ниже графике приводит к созданию сильно связанных компонентов, как показано на рисунке.Вершина 0 в сокращенном DAG достижима из любой другой вершины.

То, что я нигде не смог найти, это детали, которые я представил выше.Такие комментарии, как «ну, это легко, сделай это, затем сделай что-нибудь еще», выкладываются без конкретных подробностей.