Re: [jgrapht-users] Average path length

[Claudio M. <cla...@gm...>]

yes, that's what i want. i guess i should first transform my graph
into adjacent matrix representation in order to do so. Is there an
efficient way in jgrapht?

On Wed, Apr 29, 2009 at 9:10 PM, John V. Sichi <js...@gm...> wrote:
> 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
>>
>>
>
>



-- 
    Claudio Martella
    cla...@gm...