Graph construction performance

Specific Domains Graphs
1

I need to construct a dense weighted undirected graph with ~20,000 vertices. Currently, I have the following code

using LightGraphs, SimpleWeightedGraphs

function main(n)
   g = SimpleWeightedGraph(n)

   for u ∈ vertices(g)
      for v ∈ (u+1):nv(g)
         add_edge!(g, u, v, rand())
      end
   end
end

julia> @time main(10)
  0.000014 seconds (22 allocations: 4.969 KiB)

julia> @time main(100)
  0.005794 seconds (36 allocations: 515.250 KiB)

julia> @time main(1000)
 86.207979 seconds (48 allocations: 18.017 MiB, 0.01% gc time)

which scales poorly.

Can anyone tell me what am I doing wrong and help me to resolve this performance issue so that I can run it for 20,000 vertices?

2 Likes
2

In general, graphs have the same problem as sparse matrices (because that’s basically what they are): you pretty much have to heap allocate everything unless you know ahead of time exactly where the non-zero elements (edges) will be.

In your case, you are starting out with a sparse matrix and adding literally every element one by one, instead of starting out with a matrix of ones. What you have here is literally the worst case scenario.

LightGraphs has a slew of graph constructor functions to efficiently or conveniently construct lots of graphs. I don’t see a fully connected graph though (unless I’m missing it?)).

Regardless, the graph constructs efficiently from adjacency matrices.

julia> @btime SimpleGraph(ones(1000,1000));
  28.766 ms (10012 allocations: 39.03 MiB)

Depending on what you’re doing, you may want to define AbstractMatrix types that give the matrix you want without actually having to allocate it (one of the killer features of Julia is that this is very, very easy to do). (Note also that my example has self-edges.) Depending on what you’re doing it might even be worth defining a custom AbstractGraph type which is connected by default.

Off the top of my head I’m not sure what the best way of dealing with the weights is, but I know they can be set after construction.

4 Likes
3

If you want to build a graph edge by edge, the MetaGraphs package would be faster, but the graph traversal making use of the weights may be slower. Instead you would use add_edge!(g, src, dst, :weight, edgeweight) to add the the metadata.

1 Like