Get all Paths between 2 Nodes in a simple graph using JGraphT

968 views Asked by At

I' m currently studying the JGraphT libraries to manipulate Graphs in Java, in particular I'm trying to identify the longest path between 2 nodes in a simple graph and I know that I can get there by using a recursive method. Anyway, I found in Java docs the AllDirectedGraphs library that can handle the job in case of directed graphs, here' s a simple example:


//the nodes of the graph are countries and the edges are the routes that connect the countries by land

AllDirectedPaths<Country, DefaultEdge> paths = new AllDirectedPaths<Country, DefaultEdge(graph);

//getting all the paths between 2 random countries
         
List<GraphPath<Country, DefaultEdge>> longestPath = paths.getAllPaths(countries.get(220), countries.get(325), true, null);

GraphPath<Country, DefaultEdge> obj = null;
double maxlenght=0;
         
for( GraphPath<Country, DefaultEdge> pa :longestPath ) {
                     
         if(pa.getLength()>maxlenght)
             obj= pa;
        }
return obj;
}

Obviously using an undirected graph with the same method throw an Exception, so I' m wondering if there is a similar workaround with a simple graph, since I can' t find it by my self .

0

There are 0 answers