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

[Tamas Nepusz]

> 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.

Cheers,
T.