[Lemon-user] questions

[Alpár Jüttner]

On Fri, 2009-05-15 at 15:10 -0500, Ilya Safro wrote:
> Dear authors of LEMON library,
> 
> I'm thinking to use your software but I've couple of very basic 
> questions.

> What is the maximum number of edges and nodes that your 
> library allows for undirected graphs?

It is not fixed and may depend on the architecture and the actual graph
implementation you use. Currently both ListGraph and SmartGraph uses
signed int for the node/arc ids. On an 32 or 64 bit intel architecture
it means you can theoretically have at most

2^31=2147483648 nodes and
2^30=1073741824 edges,

Of course these limits can only be achieved on a 64 bit system with tens
of GB-s (see below)

>  What is the approximate size of 
> the graph your library will allow for 1Gb of memory?

It depends again. Each graph class has some minimal memory footprint
even when it is empty, but it is negligible. Beyond that each edge/arcs
needs additional memory, namely
ListGraph needs 16 bytes (size of 4 ints) per node and 24 bytes (6 ints)
per edge.
SmartGraph needs 6 bytes (4 ints) per node and 16 bytes (4 ints) per
edge.

Of course, if you want to assign data to the edges/nodes it will need
additional space in your memory.

Regards,
Alpar