Re: [jgrapht-users] Average path length

[John V. S. <js...@gm...>]

Hi Claudio,

You probably want to first run an all-pairs shortest path algorithm such 
as Floyd-Warshall and then analyze the results from that.

http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm

JGraphT does not yet have this in the library.

JVS

Claudio Martella wrote:
> Hello list!
> 
> I'm trying to calculate the average path length of my graph and the
> diameter (longest shortest path).
> 
> At the moment it's non-optimized:
> 
> for(Vertex source: graph.vertexSet()){
>     for(Vertex destination: graph.vertexSet()){
>         if(!source.equals(destination)){
>             List<DefaultWeightedEdge> path =
> DijkstraShortestPath.findPathBetween(graph, source, destination);
>             if(path != null)
>                 averagePathLength += path.size();
>         }
>     }
> }
> N = graph.vertexSet().size();
> averagePathLength /= (N*(N-1));
> 
> This code is simplified to explain you what I'm doing now. There's of
> course a misusage of resources and computational time. Any idea what
> is the best way to calculate average path lengths, diameter and every
> kind of graph property that would need to calculate paths reusing
> resources and partial solutions?
> 
> TIA
> 
> /CM
> 
>