Tarjan算法实现,低值节点问题

huangapple go评论80阅读模式
英文:

Tarjan's Algorithm implementation, Low value node issue

问题

我正在尝试在图的一组节点上执行Tarjan算法,我可以成功找到强连通分量(SCC),但是根节点或低值节点始终不正确,即使对于只有一个元素的SCC,根节点也不匹配该元素。
例如:

0-3 是低值节点
[82-97]
529-529 是低值节点
[69-81]
379-379 是低值节点
[57-68]
1619-1619 是低值节点
[136-137]
415-415 是低值节点
[45-56]

顶部是低值节点,底部是组成SCC的单个元素

我目前的代码如下:

package Structs;

import java.util.*;

public class TarjanSCC {

    private int id;
    private boolean[] onStack;
    private int[] ids, low;
    private Deque<Integer> stack;
    private Graph<BasicBlock> graph;
    private Map<BasicBlock, Integer> nodeMap;
    private BasicBlock[] nodes;
    private static final int UNVISITED = -1;

    public TarjanSCC(Graph<BasicBlock> graph) {
        this.graph = graph;
    }

    public void runTSCC() {
        runTSCC(graph);
    }

    public void runTSCC(Graph<BasicBlock> nodeGraph) {

        // 初始化排序所需的值
        this.nodes = nodeGraph.getNodes().toArray(new BasicBlock[nodeGraph.size()]);
        int size = nodes.length;
        this.ids = new int[size];
        this.low = new int[size];
        this.onStack = new boolean[size];
        this.stack = new ArrayDeque<>();
        this.nodeMap = new HashMap<>();

        // 将所有节点标记为未使用,并将节点放入映射中,以便可以轻松地从节点检索索引
        for (int i = 0; i < size; i++) {
            nodeMap.put(nodes[i], i);
            ids[i] = UNVISITED;
        }

        // 对每个未访问的节点调用DFS算法
        for (int i = 0; i < size; i++) {
            if (ids[i] == UNVISITED) dfs(i, nodeGraph);
        }
    }

    private void dfs(int at, Graph<BasicBlock> nodeGraph) {
        ids[at] = low[at] = id++;
        stack.push(at);
        onStack[at] = true;

        // 访问所有图的邻居,并标记为已访问并添加到堆栈中
        for (BasicBlock edge : nodeGraph.getEdges(nodes[at])) {
            int nodeArrayIndex = nodeMap.get(edge);
            if (ids[nodeArrayIndex] == UNVISITED) {
                dfs(nodeArrayIndex, nodeGraph);
                low[at] = Math.min(low[at], low[nodeArrayIndex]);
            } else if (onStack[nodeArrayIndex]) low[at] = Math.min(low[at], nodeArrayIndex);
        }

        // 我们已经访问了所有邻居,现在开始将堆栈清空,直到达到SCC的起点
        if (low[at] == ids[at]) {
            List<BasicBlock> sccList = new ArrayList<>();
            for (int node = stack.pop(); ; node = stack.pop()) {
                onStack[node] = false;
                sccList.add(0, nodes[node]);
                if (node == at) {
                    System.out.println(nodes[low[at]] + " 是低值节点");
                    System.out.println(sccList);
                    break;
                }
            }
        }
    }
}

我怀疑问题在于设置低值节点。不需要其他类信息,因为从图中检索边没有问题。

英文:

I am trying to execute tarjans algorithm on a set of nodes from a graph, I can succesfully find Strongly Connected Components, however the root or the low value node is always off, even for SCC's with only 1 element the root node does not match that element
For Example:

0-3 IS LOW VALUE NODE
[82-97]
529-529 IS LOW VALUE NODE
[69-81]
379-379 IS LOW VALUE NODE
[57-68]
1619-1619 IS LOW VALUE NODE
[136-137]
415-415 IS LOW VALUE NODE
[45-56]

where the top is the low value node and the bottom is the 1 element that makes up the SCC

The code I currently have is here

package Structs;
import java.util.*;
public class TarjanSCC {
private int id;
private boolean[] onStack;
private int[] ids, low;
private Deque&lt;Integer&gt; stack;
private Graph&lt;BasicBlock&gt; graph;
private Map&lt;BasicBlock, Integer&gt; nodeMap;
private BasicBlock[] nodes;
private static final int UNVISITED = -1;
public TarjanSCC(Graph&lt;BasicBlock&gt; graph) {
this.graph = graph;
}
public void runTSCC() {
runTSCC(graph);
}
public void runTSCC(Graph&lt;BasicBlock&gt; nodeGraph) {
//Initialize values for sorting
this.nodes = nodeGraph.getNodes().toArray(new BasicBlock[nodeGraph.size()]);
int size = nodes.length;
this.ids = new int[size];
this.low = new int[size];
this.onStack = new boolean[size];
this.stack = new ArrayDeque&lt;&gt;();
this.nodeMap = new HashMap&lt;&gt;();
//Mark all nodes as unused, place nodes in a map so index is easily retrievable from node
for(int i = 0; i &lt; size; i++) {
nodeMap.put(nodes[i], i);
ids[i] = UNVISITED;
}
//Invoke the DFS algorithm on each unvisited node
for(int i = 0; i &lt; size; i++) {
if (ids[i] == UNVISITED) dfs(i, nodeGraph);
}
}
private void dfs(int at, Graph&lt;BasicBlock&gt; nodeGraph) {
ids[at] = low[at] = id++;
stack.push(at);
onStack[at] = true;
//Visit All Neighbours of graph and mark as visited and add to stack,
for (BasicBlock edge : nodeGraph.getEdges(nodes[at])) {
int nodeArrayIndex = nodeMap.get(edge);
if (ids[nodeArrayIndex] == UNVISITED) {
dfs(nodeArrayIndex, nodeGraph);
low[at] = Math.min(low[at], low[nodeArrayIndex]);
}
else if (onStack[nodeArrayIndex]) low[at] = Math.min(low[at], nodeArrayIndex);
}
//We&#39;ve visited all the neighours, lets start emptying the stack until we&#39;re at the start of the SCC
if (low[at] == ids[at]) {
List&lt;BasicBlock&gt; sccList = new ArrayList&lt;&gt;();
for (int node = stack.pop();; node = stack.pop()) {
onStack[node] = false;
sccList.add(0, nodes[node]);
if (node == at) {
System.out.println(nodes[low[at]] + &quot; IS LOW VALUE NODE&quot;);
System.out.println(sccList);
break;
}
}
}
}
}

I suspect the issue lies with setting the low values.
I do not believe any other class info is required as there is no issues with retrieving edges from the graph

答案1

得分: 0

我错误地索引了根节点,nodes[at] 是访问根节点的正确方式。

英文:

I was indexing the root node wrong nodes[at] is the proper way to access the root node

huangapple
  • 本文由 发表于 2020年8月14日 08:25:21
  • 转载请务必保留本文链接:https://go.coder-hub.com/63404896.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定