Re: [igraph] the old "cannot reserve space for vector" problem

[Pascal Jürgens]

Hello,

sorry to hijack this thread, but my question is related.

Are there any practical limits to using shortest_paths() with much larger 
networks? Especially, are there memory leaks and / or other limits when using 
the python interface? 

I'd like to compute it on a network with 80k vertices. Since the algorithm has 
quadratic memory requirements, this results in around 50GB of RAM. As long as 
there are no serious leaks, this is a small enough amount to run on a quad 
memory EC2 instance. Using the unweighted algorithm (is it Johnson's?) with 
O(n(V+E)), this seems feasible. Or will the time complexity bite me before the 
RAM does?

Pascal

On Jun 5, 2010, at 11:29 , Tamas Nepusz wrote:

> By the way, the shortest path matrix of a graph with 18209 vertices has 
> 331567681 elements; if each element takes up 8 bytes, then the total memory 
> requirement for storing the whole matrix at once will be about 2.47Gb, so the 
> trick suggested by Łukasz might also work.