Re: [igraph] igraph maximum number of graph nodes or edges

[Gábor Csárdi]

On Fri, Apr 20, 2012 at 6:13 AM, Tamas Nepusz <address@hidden> wrote:
>
>> What practical limits are there to graph size in terms of nodes and
>> edges? For example does igraph creates an adjacency matrix as a single
>> block like malloc(n * n), then sqrt(n) must be smaller than INT_MAX etc?
> igraph does not use adjacency matrices (luckily), so that shouldn't be a
> problem. igraph uses an indexed edge list representation under the hood;
> basically we have a long edge list, two first-level indices to keep the edge
> list sorted by source and target vertices, and two second-level indices to
> allow us to jump into the first-level index right at the places where the
> edges incident on a given vertex start. In the end, the graph itself
> requires 32 bytes per edge and 16 bytes per vertex since all the slots in
> the edge list and the indices are C doubles (so they take up 8 byte per
> slot). Of course most of the algorithms also have additional memory
> requirements.
>
>> Also if known, does the VF2 implementation add additional constraints on
>> this?
> A quick glance into the VF2 source code in topology.c seems to indicate that
> the algorithm creates two lazy adjacency list representation of both graphs
> on-the-fly (because it is faster to work with in this particular case). In
> the worst case, the lazy adjacency list expands to the full adjacency list
> of the graph, which should take one igraph_vector_t by vertex and one C
> double per edge. An igraph_vector_t contains three pointer, and you need 8
> bytes per pointer on a 64-bit platform (4 bytes on a 32-bit one). That's 24
> bytes per vertex and 8 bytes per edge, worst case. VF2 also needs some extra
> vectors which are typically in the order of O(|V|) where |V| is the number
> of vertices.
>
> So, let's say that you have N vertices and M edges in both graphs. You need
> 32*M+16*N to store each of the graphs, plus 2*(24*N+8*M) to store the
> adjacency lists for each of the graphs. This is 96 bytes per edge and 128
> bytes per vertex in the worst case (if all the lazy adjacency lists have to
> be expanded in full) if I calculated it correctly. Constant factors are
> neglected.

Consider also that VF2 is an algorithm with exponential time
complexity, so it will not work for large (or even moderate) graph
sizes, because it just simply takes too long to run.

Gabor

[...]

-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI