Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to use the DepthFirstSearchIterator class to run a depth first search on a graph using JGraphT

I am experimenting with JGraphT and have hit a brick wall trying to implement a depth first search using the JGraphT API. I have created a simple graph with nodes and vertices's as follows:

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

How would I use the DepthFirstSearchIterator to run DFS on this graph? Kind regards

like image 372
insudo Avatar asked Nov 22 '13 13:11

insudo


1 Answers

Just traverse the graph using DepthFirstSearchIterator. Here is an example:

import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.traverse.DepthFirstIterator;
import org.jgrapht.traverse.GraphIterator;

public class GraphDemo {

    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 DepthFirstIterator<Integer, DefaultEdge>(graph);
        while (iterator.hasNext()) {
            System.out.println( iterator.next() );
        }
    }
}

For more control, you can attach TraversalListener to the iterator using addTraversalListener(). Here is an example of a basic listener.

like image 53
tenorsax Avatar answered Oct 15 '22 19:10

tenorsax