Jgrapht - tracking DepthFirstSearch iterator backtracks

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Jgrapht - tracking DepthFirstSearch iterator backtracks

Traven
Hi, I am writing in regards to this question, that I posted on stackoverflow and couldn't get any answer:

http://stackoverflow.com/questions/30938461/jgrapht-tracking-depthfirstsearch-iterator-backtracks

Copy of stack's question content is below:

I am trying to use jgrapht DepthFirstIterator to traverse through graph and find ANY path leading from start node to the target node.

As far as I understand, iterator traverses from vertex to vertex and when it cannot go any deeper, it backtracks and tries other paths (depth-first search algorithm).

I know that you cant iterate through the nodes in this way:

iterator = new DepthFirstIterator<Integer, DefaultEdge>(graph);
    while (iterator.hasNext()) {
        ...
    }

My question is:
1. How in jgrapht save the final path found by this algorithm? I can break the loop after I've found the target node, although I dont have any good ideas of how to save the edges leading to the solution. I cannot save every traversed edge, because it will also add all the backtracks to my result.
2. Also, is the Depth First Search Iterator protected against running into the infinite loop when encountering cycles?

Any help/suggestions highly appreciated :).