CODEWITHSUNDEEP
javagraphjgrapht
TheMP
TheMP

Reputation: 8427

JGraphT - Finding path with BreadthFirstIterator

Here is the code to traverse the graph with BreathFirstIterator:

public class GraphTest {

    public static void main(String[] args) {
        DirectedGraph<Integer, DefaultEdge> graph = 
            new DefaultDirectedGraph <Integer, DefaultEdge>(DefaultEdge.class);

        graph.addVertex(7);
        graph.addVertex(4);
        graph.addVertex(9);
        graph.addVertex(3);
        graph.addVertex(2);
        graph.addVertex(5);


        graph.addEdge(7, 4);
        graph.addEdge(7, 9);
        graph.addEdge(9, 3);
        graph.addEdge(3, 2);
        graph.addEdge(3, 5);

        GraphIterator<Integer, DefaultEdge> iterator = 
                new BreadthFirstIterator<Integer, DefaultEdge>(graph);
        while (iterator.hasNext()) {
            System.out.println( iterator.next() );
        }
    }
}

As expected, the code prints out the list of all visited vertexes: 7,4,9,3,2,5. My problem is - I don't know how can I use this API to obtain a path with removed backtracks of algorithm. For example, for path from 7 to 2, it would output 7->9->3->2, and not just the list of visited vertexes. Stopping it after reaching the destination is obsiously not enough. Have anyone already solved this issue?

Upvotes: 1

Views: 3083

Answers (1)

Tunaki
Tunaki

Reputation: 137084

It is possible to get the shortest path between two vertices with DijkstraShortestPath.findPathBetween. It provides an implementation of Dijkstra's shortest path algorithm using ClosestFirstIterator. If there is no such path, it will return null.

Sample code:

DirectedGraph<Integer, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

graph.addVertex(7);
graph.addVertex(4);
graph.addVertex(9);
graph.addVertex(3);
graph.addVertex(2);
graph.addVertex(5);

graph.addEdge(7, 4);
graph.addEdge(7, 9);
graph.addEdge(9, 3);
graph.addEdge(3, 2);
graph.addEdge(3, 5);

List<DefaultEdge> path = DijkstraShortestPath.findPathBetween(graph, 7, 2);
System.out.println(path); // prints [(7 : 9), (9 : 3), (3 : 2)]

Upvotes: 1

Related Questions