[Haskell-cafe] Inductive graphs memory usage

[Ronald Guida]

On Thu, Jul 10, 2008 at 4:57 PM, Andre Nathan <andre at digirati.com.br> wrote:
> Hello
>
> I'm trying to create a directed graph using the Data.Graph.Inductive.
> The graph is a random graph using the G(n, p) model, that is, each of
> the n nodes is linked to every other node with probability p.

So the average degree of a single node is p * n, and the expected
number of edges in the entire graph will grow as O(n ^2).

> I'm seeing a large increase of memory usage when n grows (this is using
> p = 0.1):
>
> n = 1000 ->  96MB
> n = 2000 -> 283MB
> n = 3000 -> 760MB
>
> So, I'm probably doing something very stupid :)

Your ratios are about 1 : 3 : 8.
That pretty close to quadratic growth, 1 : 4 : 9, so I think all is well.