Re: [igraph] How to add a vertex using the id, High memory usage when using igraph_vector_t?

[Gábor Csárdi]

Hi Laurence,

On Thu, Mar 5, 2009 at 11:43 PM, Muller, L.Y.L. <address@hidden> wrote:
> Hi,
>
> in order to analyze a large data set, I'm trying to load the graph into
> igraph.
> However, this fails due the following two issues that are described below.
>
> Question 1:
> ===========
> Is it possible to add a node (vertex) by id?
>
> Example:
> --------
> If I have the following dataset (node ids): {0, 1, 3, 4, 5}
>
> Using this igraph function: igraph_add_vertices(&igraph_graph, 5, 0);
> Would result in a dataset like this {0, 1, 2, 3, 4}.
>
> When adding edges to the graph that are connected to node 5, igraph will
> return an error or crash because node id 5 is not in the vertex list.
> (Also, id 2 shouldn't be part of the list).
>
> How can should I solve this problem in igraph?

igraph vertex ids are always consecutive integers. Basically you have
two choices. First, modify your data set to satisfy this criteria.
Second, use vertex attributes to keep track of the "real" vertex ids.
Using attributes from C is not very convenient, but it is possible. It
is much easier from R or Python.

> Question 2:
> ===========
> For some reason the igraph_vector_t is using more memory than a std::vector.
> When attempting to load the graph described below, igraph seems to run out
> of memory. Is there some (size) limit in igraph_vector_t and which method
> should I use to load a large graph?
>

There is no memory limit in igraph. For igraph_vector_t, however, the
whole vector must be a single piece of memory. This is also true for
all the std::vector implementations I've seen, so this is probably not
the main difference. The difference might be that igraph_vector_t
stores doubles, this means 8 bytes per entry, whereas if you have a
std::vector of 'int', that is only 4 bytes per entry, at least on most
platforms. So because of this igraph_vector_t needs twice as much
memory.

Another thing is that it is more efficient to allocate the whole chunk
of memory for the igraph_vector_t first, i.e. calling
igraph_vector_init() with the appropriate size. Otherwise igraph keeps
resizing it as you add more elements. The resizing algorithm allocates
double amount of memory if the vector is full, this means that you
might allocate twice more than you actually need.

If you want to do anything with such a big graph, I would recommend to
buy more memory. Even if the graph fits into the memory, you probably
want to make come calculations on it and this requires additional
memory allocations.

The igraph_t structure needs space for 4*E+2*V doubles, E is the
number of edges, V the number of vertices. That means about 1.3Gb for
your graph.

Best,
Gabor

[...]

-- 
Gabor Csardi <address@hidden>     UNIL DGM