[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) |

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