Quantcast

Re: APSP problem.

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: APSP problem.

Richard Adams
Hi,
I have a basic implementation of the   Floyd Warshall algorithm. On a
9000 node graph all pairs are calculated
in ~ 36h using a 4Ghz / 4Gb memoerySun cluster. You are welcome to it
but it is entirely independent of jgrapht,
I am only an infrequent jgrapht user so would need some help in
converting it. You are welcome to it as is.
The algorithm stores distances in a byte [][] - so e.g., a 9000 node
graph needs an 81Mb array.

It is much faster than running DjisktraSP repeatedly - I have access to
a parallel computing cluster and even running
DSP on 8 threads is not faster than FW.
Regards
Richard

[hidden email] wrote:

>Send jgrapht-users mailing list submissions to
> [hidden email]
>
>To subscribe or unsubscribe via the World Wide Web, visit
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>or, via email, send a message with subject or body 'help' to
> [hidden email]
>
>You can reach the person managing the list at
> [hidden email]
>
>When replying, please edit your Subject line so it is more specific
>than "Re: Contents of jgrapht-users digest..."
>
>
>Today's Topics:
>
>   1. List of all Diskstra's distance from a given source to all points
>       in the graph (Julien Thomas de Boer)
>   2. Re: List of all Diskstra's distance from a given
>       source to all points in the graph (John V. Sichi)
>
>--__--__--
>
>Message: 1
>From: Julien Thomas de Boer <[hidden email]>
>To: [hidden email]
>Date: Tue, 02 Aug 2005 13:40:33 +0200
>Subject: [jgrapht-users] List of all Diskstra's distance from a given source to all points
> in the graph
>
>Hi everyone,
>I want to compute the mean distance in a Jgrapht graph. So, I have to
>compute distances for each possible pairs in the graph. But computing
>Dijsktra for each pairs is taking too much time. I heard that
>Dijkstra didnt give you only  the shortest path between the source node
>and the target node but also between the source and all nodes in the
>graph at the same time. is it the case in the current implementation of
>dijkstra in Jgraht? If yes, how can I retrieve this list of distances.
>Thanks for your help.
>
>
>  
>

--
Dr Richard Adams
Psychiatric Genetics Group,
Medical Genetics,
Molecular Medicine Centre,
Western General Hospital,
Crewe Rd West,
Edinburgh UK
EH4 2XU

Tel: 44 131 651 1084
[hidden email]





Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: APSP problem.

John Sichi
Administrator
Hi Richard,

Please add your code "as is" via the Feature Request System:

http://sourceforge.net/tracker/?atid=579690&group_id=86459&func=browse

Then eventually someone who needs it can convert and incorporate it into
JGraphT.

Thanks,
JVS

Richard Adams wrote:

> Hi,
> I have a basic implementation of the   Floyd Warshall algorithm. On a
> 9000 node graph all pairs are calculated
> in ~ 36h using a 4Ghz / 4Gb memoerySun cluster. You are welcome to it
> but it is entirely independent of jgrapht,
> I am only an infrequent jgrapht user so would need some help in
> converting it. You are welcome to it as is.
> The algorithm stores distances in a byte [][] - so e.g., a 9000 node
> graph needs an 81Mb array.
>
> It is much faster than running DjisktraSP repeatedly - I have access to
> a parallel computing cluster and even running
> DSP on 8 threads is not faster than FW.
> Regards
> Richard
>
> [hidden email] wrote:
>
>> Send jgrapht-users mailing list submissions to
>>     [hidden email]
>>
>> To subscribe or unsubscribe via the World Wide Web, visit
>>     https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>> or, via email, send a message with subject or body 'help' to
>>     [hidden email]
>>
>> You can reach the person managing the list at
>>     [hidden email]
>>
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of jgrapht-users digest..."
>>
>>
>> Today's Topics:
>>
>>   1. List of all Diskstra's distance from a given source to all points
>>       in the graph (Julien Thomas de Boer)
>>   2. Re: List of all Diskstra's distance from a given
>>       source to all points in the graph (John V. Sichi)
>>
>> --__--__--
>>
>> Message: 1
>> From: Julien Thomas de Boer <[hidden email]>
>> To: [hidden email]
>> Date: Tue, 02 Aug 2005 13:40:33 +0200
>> Subject: [jgrapht-users] List of all Diskstra's distance from a given
>> source to all points
>> in the graph
>>
>> Hi everyone,
>> I want to compute the mean distance in a Jgrapht graph. So, I have to
>> compute distances for each possible pairs in the graph. But computing
>> Dijsktra for each pairs is taking too much time. I heard that Dijkstra
>> didnt give you only  the shortest path between the source node
>> and the target node but also between the source and all nodes in the
>> graph at the same time. is it the case in the current implementation of
>> dijkstra in Jgraht? If yes, how can I retrieve this list of distances.
>> Thanks for your help.
>>
>>
>>  
>>
>


Loading...