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