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, i.e for example for path from 7 to 2: 7->9->3->2), not just the list of visited vertexes. Stopping it after reaching the destination is obviously not enough. Have anyone already solved this issue? |
If you need a path in a given graph use the relevant method of any of the shortest path algorithm implementations, such as DijkstraShortestPath.findPathBetween(graph, source, destination).
Üdvözlettel, Besenyei Szabolcs 2015-10-04 17:20 GMT+02:00 Traven <[hidden email]>: Here is the code to traverse the graph with BreathFirstIterator: ------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
I'm sorry, I tried to simplify the case too much and made it unreadable. My core in reality looks more like this:
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> (DefaultWeightedEdge.class); graph.addVertex("1"); graph.addVertex("2"); graph.addVertex("3"); graph.addVertex("4"); graph.addVertex("5"); DefaultWeightedEdge e1 = graph.addEdge("1", "2"); graph.setEdgeWeight(e1, 5); DefaultWeightedEdge e2 = graph.addEdge("2", "3"); graph.setEdgeWeight(e2, 10); DefaultWeightedEdge e3 = graph.addEdge("2", "4"); graph.setEdgeWeight(e3, 2); DefaultWeightedEdge e4 = graph.addEdge("4", "5"); graph.setEdgeWeight(e4, 2); DefaultWeightedEdge e5 = graph.addEdge("5", "3"); graph.setEdgeWeight(e5, 2); System.out.println("Shortest path from vertex 1 to vertex 5:"); List shortest_path = DijkstraShortestPath.findPathBetween(graph, "1", "3"); System.out.println(shortest_path); } In this case Dijkstra returns the correct, shortest path: 1->2->4->5->3. My problem is - for the same graph, I want to obtain the path containing the fewest number of transfers between vertices (in this case it would be 1->2->3). For this use-case the BFS would be the perfect solution. Is there a way to somehow use the BreadthFirstIterator from jgrapht API or do I have to write an algorithm by myself? |
Free forum by Nabble | Edit this page |