CODEWITHSUNDEEP
javagraphjgrapht
TheMP
TheMP

Reputation: 8427

jgrapht - get list of all traversed nodes

Here is the sample code for finding the shortest path with Dijkstra algorithm:

public static void main(String args[]) {
    SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
    graph.addVertex("vertex1");
    graph.addVertex("vertex2");
    graph.addVertex("vertex3");
    graph.addVertex("vertex4");
    graph.addVertex("vertex5");

    DefaultWeightedEdge e1 = graph.addEdge("vertex1", "vertex2");
    graph.setEdgeWeight(e1, 5);

    DefaultWeightedEdge e2 = graph.addEdge("vertex2", "vertex3");
    graph.setEdgeWeight(e2, 3);

    DefaultWeightedEdge e3 = graph.addEdge("vertex4", "vertex5");
    graph.setEdgeWeight(e3, 6);

    DefaultWeightedEdge e4 = graph.addEdge("vertex2", "vertex4");
    graph.setEdgeWeight(e4, 2);

    DefaultWeightedEdge e5 = graph.addEdge("vertex5", "vertex4");
    graph.setEdgeWeight(e5, 4);

    DefaultWeightedEdge e6 = graph.addEdge("vertex2", "vertex5");
    graph.setEdgeWeight(e6, 9);

    DefaultWeightedEdge e7 = graph.addEdge("vertex4", "vertex1");
    graph.setEdgeWeight(e7, 7);

    DefaultWeightedEdge e8 = graph.addEdge("vertex3", "vertex2");
    graph.setEdgeWeight(e8, 2);

    DefaultWeightedEdge e9 = graph.addEdge("vertex1", "vertex3");
    graph.setEdgeWeight(e9, 10);

    DefaultWeightedEdge e10 = graph.addEdge("vertex3", "vertex5");
    graph.setEdgeWeight(e10, 1);

    System.out.println("Shortest path from vertex1 to vertex5:");
    List<DefaultWeightedEdge> shortest_path = DijkstraShortestPath.findPathBetween(graph,"vertex1", "vertex5");
    System.out.println(shortest_path);
}

Is there a possibility to get a list of nodes that have been reached and marked as visited by the algorithm? I've seen that there is something called TraversalListener, but it looks like applies only to iterators, like BreadthFirstIterator.

Upvotes: 1

Views: 451

Answers (1)

Tunaki
Tunaki

Reputation: 137084

It looks like there is no facility for this using DijkstraShortestPath class. This is because traversal listener are added to graph iterator and the iterator used by DijkstraShortestPath can't be accessed.

As such, the only solution would be to copy DijkstraShortestPath code into a new class (let's call it MyDijkstraShortestPath) and add the traversal listener.

First, you need to create a class MyTraversalListener that inherits from TraversalListenerAdapter, and override the method you want.

class MyTraversalListener<V, E> extends TraversalListenerAdapter<V, E> {
     // override the method you want, like vertexTraversed and edgeTraversed
}

Then, in the constructor of our new MyDijkstraShortestPath class, we need to add it:

ClosestFirstIterator<V, E> iter =
    new ClosestFirstIterator<V, E>(graph, startVertex, radius);
iter.addTraversalListener(new MyTraversalListener<V, E>());

Upvotes: 1

Related Questions