[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Shortest paths on very large graphs

From: Gabor Csardi
Subject: Re: [igraph] Shortest paths on very large graphs
Date: Fri, 11 Jul 2008 04:11:05 -0500
User-agent: Mutt/1.5.17+20080114 (2008-01-14)


you can calculate the memory requirement like this: 
|V|^2 * 8 / 1024 / 1024 * 2
this roughly gives the requires memory in megabytes, the final *2
is needed because the result matrix is copied once.

If you don't have that much memory then call shortest.paths() 
for a single vertex (or a small number of vertices, like 10)
at a time and store/use the results before 
calling it for the next vertex. You can run this a couple 
of times to make an estimate for how much it would take for the 
whole graph.

get.shortest.paths() is slower than shortest.paths() because 
it also keeps track of the paths themselves. It also requires *much* 
more memory for the same number of source vertices.

Buying more memory is not an option? Memory is cheap and 
the computation is fine if you have 16Gb, maybe even for 8Gb.


On Thu, Jul 10, 2008 at 11:51:20PM +0100, Vassilis Kostakos wrote:
> Dear all,
> I am using igraph version 0.6 in R to analyse weighted and directed  
> graphs with more than 20000 nodes.  As part of my analysis i need to  
> calculate the shortest paths between all pairs of nodes.  Simply calling 
> shortest.paths(g)  fails because it requires too much memory.  On the 
> other hand, running
> len<-length(V(g))-1
> for(i in 0:len){for (j in 0:len){
>  get.shortest.paths(g,i,j)
> }}
> is just too slow in R.
> Can anyone suggest how I can speed this up without reverting to C  
> programming?
> Thanks
> --
> Vassilis Kostakos
> address@hidden
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

Csardi Gabor <address@hidden>    UNIL DGM

reply via email to

[Prev in Thread] Current Thread [Next in Thread]