CODEWITHSUNDEEP
javagraph-traversaljgrapht
Hector
Hector

Reputation: 5354

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?)

Upvotes: 1

Views: 1261

Answers (2)

Mike H
Mike H

Reputation: 239

You can use EdgeReversedGraph to create a "edge-reversed" view (i.e. sources are now targets and vice versa) then use the same iterators as you use for the normal graph.

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

}

Upvotes: 2

Joris Kinable
Joris Kinable

Reputation: 2411

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.

Upvotes: 2

Related Questions