Re: [igraph] Shortest paths on very large graphs

[Gabor Csardi]

Vassilis, 

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.

Gabor

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