[R] allShortestPath function in e1071 package

Friedrich.Leisch@ci.tuwien.ac.at Friedrich.Leisch at ci.tuwien.ac.at
Fri Sep 26 09:42:49 CEST 2003

>>>>> 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.


More information about the R-help mailing list