10 Jul
2008
10 Jul
'08
6:32 p.m.
On Thu, Jul 10, 2008 at 4:57 PM, Andre Nathan
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.