[Lemon-user] max number of arcs in ListDigraph

[Alpár Jüttner]

Hi,

> What is the max number of arcs that a ListDigraph can take?

There are two limitations

     1. Both the number of edges and the number of arcs are limited by
        INT_MAX, which is 2^31 on most system (even using 64 bit CPU)
     2. Memory limitation. ListDiraph basically needs 4*sizeof(int)=16
        bytes per node and 6*sizeof(int)=24 bytes per arcs. They are
        actually stored in std::vector<>s, so there is an overhead
        imposed by std::vector<> itself (due to its proactive allocation
        scheme). It is hard to predict, but I found that Linux memory
        allocation scheme is very good at mitigating this effect.

>    int nArcs = 2000000;
>    cout << "nArcs is equal to " << nArcs << endl;
>    ListDigraph::Arc  arc[nArcs];
>    cout << " All arcs are defined. "<< endl;

Here you only allocate the Arc data structure (which is basically just a
simple int) but don't add arcs to the graph. So your code will very
likely crash even if you write this:

    int arcs[nArcs];

The point is that here you probably (in fact, depending on the compiler
you use) try to allocate on the stack, the size of which is limited by
the OS. You can increase this limitation (e.g. using the Bash shell on
Linux it can be done with 'ulimit -s').
But for large arrays, you'd better use std::vector<> instead.

Regards,
Alpar