How to traverse a graph both “forwards” and “backwards”?

I am investigating Graphs/Graph Traversals using

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

Using the code below I can create a simple graph

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");      

and traverse it “forwards”

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

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

}

However I would also like to be able to “retrace” my steps back through the graph from any vertex and return to the “start” of the graph.

e.g. topologicalOrderIterator.previous()

I cannot see any obvious methods within jgrapht-core?

Is reverse Graph traversal possible? (logical?)

Answer

The TopologicalOrderIterator doesn’t have a previous() method. An easy way to fix this, is to implement your own iterator which extends the TopologicalOrderIterator and which maintains a memory of items you encountered. Here is an untested, poorly formatted example:

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()}
}

In summary, you maintain 2 stacks back and front. If you move forward using the next() method, you first empty the front stack, and then ask the TopologicalOrderIterator for new elements. All items obtained with next() are pushed onto the back stack. Similarly, if you move backward using the previous() method, you pop items of the back stack. All items obtained with the previous() method are pushed onto the front stack.