如何同时遍历一个图 "forwards" 和 "backwards"？

Question

我正在调查Graphs/Graph遍历使用

compile group: 'org.jgrapht', name: 'jgrapht-core', version: '1.1.0'

使用下面的代码我可以创建一个简单的图形

final Graph<String, DefaultEdge> directedGraph = new DefaultDirectedGraph<>(DefaultEdge.class);
directedGraph.addVertex("v1");
directedGraph.addVertex("v2");
directedGraph.addVertex("v3");
directedGraph.addVertex("v4");

directedGraph.addEdge("v1", "v4");
directedGraph.addEdge("v4", "v2");
directedGraph.addEdge("v2", "v3");

并遍历它"forwards"

TopologicalOrderIterator<String, DefaultEdge> topologicalOrderIterator = new TopologicalOrderIterator<>(directedGraph);
System.out.println("topologicalOrderIterator");
while (topologicalOrderIterator.hasNext()) {

    System.out.println(topologicalOrderIterator.next());

}

不过，我也希望能够 "retrace" 从图形中的任何顶点 return 返回到图形的 "start"。

例如topologicalOrderIterator.previous()

我在 jgrapht-core?

中看不到任何明显的方法

是否可以反向遍历Graph？（逻辑？）

Answer 1

TopologicalOrderIterator 没有 previous() 方法。解决此问题的一种简单方法是实现您自己的迭代器，它扩展 TopologicalOrderIterator 并维护您遇到的项目的内存。这是一个未经测试、格式不正确的示例：

public class ReversibleTopoIterator extends TopologicalOrderIterator{
    Stack<V> back=new ...
    Stack<V> front=new ...

    public V next(){
        V v;
        if(front.isEmpty())
            v=super.next();
        else
            v=front.pop();
        back.push(v);
        return v;
    }
    public V previous(){
        V v=back.pop();
        front.push(v);
        return v;
    }
    public boolean hasNext(){return !front.isEmpty() || super.hasNext()};
    public boolean hasPrevious(){return !back.isEmpty()}
}

总之，您维护了 2 个堆栈 back 和 front。如果使用 next() 方法向前移动，则首先清空 front 堆栈，然后向 TopologicalOrderIterator 请求新元素。使用 next() 获得的所有项目都被推入 back 堆栈。同样，如果使用 previous() 方法向后移动，则会弹出 back 堆栈的项目。使用 previous() 方法获得的所有项目都被推入 front 堆栈。

Answer 2

您可以使用 EdgeReversedGraph 创建“边缘反转”视图（即源现在是目标，反之亦然），然后使用与正常图形相同的迭代器。

https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/graph/EdgeReversedGraph.html

TopologicalOrderIterator<String, DefaultEdge> topologicalOrderIterator = new TopologicalOrderIterator<>(new EdgeReversedGraph(directedGraph));
System.out.println("topologicalOrderIterator");
while (topologicalOrderIterator.hasNext()) {

    System.out.println(topologicalOrderIterator.next());

}

如何同时遍历一个图 "forwards" 和 "backwards"？

How to traverse a graph both "forwards" and "backwards"?

java

jgrapht

graph-traversal