代码之家 › 专栏 › 技术社区 › Aidenhjj

用参与的循环数标记边

digraphs graph java

Aidenhjj · 技术社区 · 6 年前

给出一个图表 G = (V, E) ,使用DFS,如何用每个边参与的简单循环数来标记每个边?当我从图中提取强连接的组件时,我已经用post顺序标记了节点,所以也许我可以以某种方式使用这些信息。

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

我似乎无法清楚地解释这件事。谁能给我指出正确的方向吗?

2 回复 | 直到 6 年前

Josef Ginerman DavidG 6 年前

如果不看完整的代码,很难给出完整的答案,但我认为这会有所帮助。请注意,提供的链接用于无向图。

我认为你应该把这个问题分成两部分:

1. 查找图形中的所有循环(将其保存在哈希表或类似文件中)

查找这些周期中的哪些包含特定节点。

解决方案1: 第一步有很多在线算法,比如 this one 这需要一些小的调整或调整 this one

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

请注意,如果您只想一次找到一个节点的答案,则此解决方案不是最优的,但如果您希望能够找到任何给定节点和任何给定时间的周期数,则此解决方案确实很好。

Aidenhjj 6 年前

Map<Node, Stack<Edge>> 属于 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);
        }
    }
}