Obtaining a path from BreadthFirstIterator

[Traven]

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?

[Szabolcs Besenyei]

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


2015-10-04 17:20 GMT+02:00 Traven <[hidden email]>:

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?



--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Obtaining-a-path-from-BreadthFirstIterator-tp4025051.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

------------------------------------------------------------------------------
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users

[Traven]

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?