R help - Sep 2003 - allShortestPath function in e1071 package

Hi All,

I am using the allShortestPath function based on Floyd's algorithm in e1071 
package. It runs great when I have less than 5000 nodes. But when I tried to 
work on more than 5000 nodes, I ran into memory problem. The problem I really 
want to solve has 10000-15000 nodes.

Does anybody know how to deal with this problem? Are there any other packages 
in R that can handle this problem? Thanks!

Bing

---------------------------------
1060 Commerce Park
Oak Ridge National Laboratory
P.O. Box 2008, MS 6480
Oak Ridge, TN 37831-6480
Phone: 865-241-0761
Email: zhangb at ornl.gov

Hi Richard,

Yes, I do need the path length and shortest path itself.

Bing
>===== Original Message From "Remington, Richard" <rnews at
kernstat.com> ====>Bing
>
>Sounds like you want path length, but....
>
>If minimum distance between any two points in a plane is equivalent in
>your application, then try something like
>
>x <- runif(10)
>y <- runif(10)
>require(mva)
>min(dist(c(x,y)))
>
>When this runs out of RAM, I call a C function to do the same.  Finds
>minimum distance for 100,000 points in 1 minute on 2GHz processor, 1Gb
>RAM machine.
>
>regards,
>Richard
>
>Richard E. Remington III
>Statistician
>KERN Statistical Services, Inc.
>PO Box 1046
>Boise, ID 83701
>Tel: 208.426.0113
>KernStat.com
>
>Bing Zhang wrote:
>
>>Hi All,
>>
>>I am using the allShortestPath function based on Floyd's algorithm
in e1071
>>package. It runs great when I have less than 5000 nodes. But when I
tried to
>>work on more than 5000 nodes, I ran into memory problem. The problem I 
really
>>want to solve has 10000-15000 nodes.
>>
>>Does anybody know how to deal with this problem? Are there any other 
packages
>>in R that can handle this problem? Thanks!
>>
>>Bing
>>
>>---------------------------------
>>1060 Commerce Park
>>Oak Ridge National Laboratory
>>P.O. Box 2008, MS 6480
>>Oak Ridge, TN 37831-6480
>>Phone: 865-241-0761
>>Email: zhangb at ornl.gov
>>
>>______________________________________________
>>R-help at stat.math.ethz.ch mailing list
>>https://www.stat.math.ethz.ch/mailman/listinfo/r-help
>>
>>
>>
---------------------------------
1060 Commerce Park
Oak Ridge National Laboratory
P.O. Box 2008, MS 6480
Oak Ridge, TN 37831-6480
Phone: 865-241-0761
Email: zhangb at ornl.gov

>>>>> On Thu, 25 Sep 2003 13:04:21 -0400,
>>>>> Bing Zhang (BZ) wrote:
  > Hi All,
  > I am using the allShortestPath function based on Floyd's algorithm in
e1071
  > package. It runs great when I have less than 5000 nodes. But when I tried
to
  > work on more than 5000 nodes, I ran into memory problem. The problem I
really
  > want to solve has 10000-15000 nodes.

  > Does anybody know how to deal with this problem? Are there any other
packages
  > in R that can handle this problem? Thanks!

The e1071 implementation uses NxN matrices (where N is the number of
nodes), hence it does not scale well with the number of nodes as
memory consumption is N^2.
>From Bioconductor you get package graph which represent the graph
using lists of nedges and edges, and needs much fewer memeory if the
graphs is sparsely connected. Package RBGL (also from Bioconductor)
has shortest paths for such graph objects.

.f