用它参与的循环数标记边

Question

给定一个图 G = (V, E)，使用 DFS，我如何用它参与的简单循环数来标记每条边？当我从图中提取强连通分量时，我已经用 post-order 标记了节点，所以也许我可以以某种方式使用该信息。

private Integer labelEdges(Node currentNode, Set<Node> component) {

    Integer numLoops = 0;
    currentNode.onStack = true;

    for (Edge outEdge : currentNode.getEdges()) {
        Node nextNode = outEdge.getEnd();
        if (component.contains(nextNode)) {
            if (nextNode.onStack) {
                // loop
                numLoops += 1;
            }
            else {
                numLoops += labelEdges(nextNode, component);
            }
            outEdge.cycles = numLoops;
        }

    }
    currentNode.onStack = false;

    return numLoops;
}

这个我好像推理不清楚。谁能指出我正确的方向？

Answer 1

如果没有看到您的完整代码，很难给您一个完整的答案，但我认为这会有所帮助。请注意，提供的链接适用于无向图。

我认为你应该把问题分成两部分：

1. 查找图中的所有循环（将它们保存在散列-table 或类似的）

2. 查找那些循环中的哪些包含特定节点。

1的解决方法：第一步网上有很多算法，比如this one that would work with minor tweaks or this one就是计算循环次数，你可以改保存找到的循环。

2 的解决方案： 这取决于您如何保存循环，但这是一个简单的搜索算法。

请注意，如果您只想一次找到一个节点的答案，则此解决方案不是最佳解决方案，但如果您希望能够找到任何给定节点和任何给定的循环数，则该解决方案非常好时间.

Answer 2

我最终添加了额外的 Map<Node, Stack<Edge>> of previousEdges，以跟踪在回溯中要遍历的边。然后 unwindStack 函数遍历这个链表，递增 Edge.cycles 直到它到达结束循环的 Node (loopNode):

private void labelEdges(Node currentNode, Set<Node> component) {

    onStack.put(currentNode, Boolean.TRUE);

    for (Edge outEdge : currentNode.getEdges()) {
        Node nextNode = outEdge.getEnd();
        if (component.contains(nextNode)) {

            // put the edge on the previousEdges stack
            if (!previousEdges.containsKey(nextNode)) {
                previousEdges.put(nextNode, new Stack<>());
            }
            previousEdges.get(nextNode).push(outEdge);

            if (onStack.getOrDefault(nextNode, false)) {
                // found loop
                unwindStack(nextNode, nextNode);
                // pop the previousEdge off the stack, so that we undo any
                // overwriting of history for another branch.
                previousEdges.get(nextNode).pop();

            }
            else {
                // recursively call this function
                labelEdges(nextNode, component);
            }
        }
    }
    onStack.put(currentNode, Boolean.FALSE);
}

private void unwindStack(Node currentNode, Node loopNode) {
    Edge previousEdge;
    try {
        previousEdge = previousEdges.get(currentNode).peek();
    } catch (EmptyStackException e) {
        previousEdge = null;
    }
    if (previousEdge != null) {
        // increment edgeCycles entry by 1
        edgeCycles.merge(previousEdge, 1, Integer::sum);
        Node previousNode = previousEdge.getStart();
        if (previousNode != loopNode) {
            unwindStack(previousNode, loopNode);
        }
    }
}

用它参与的循环数标记边

Label an edge with number of cycles it participates in

java

graph

digraphs