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 Ireally>>want to solve has 10000-15000 nodes. >> >>Does anybody know how to deal with this problem? Are there any otherpackages>>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
Friedrich.Leisch@ci.tuwien.ac.at
2003-Sep-26 07:42 UTC
[R] allShortestPath function in e1071 package
>>>>> 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 graphusing 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