# Graph construction performance

**URL:** <https://discourse.julialang.org/t/graph-construction-performance/24288>\
**Category:** Graphs\
**Tags:** lightgraphs\
**Created:** [May 16, 2019, 4:48pm UTC](https://discourse.julialang.org/t/graph-construction-performance/24288 "2019-05-16T16:48:08Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Azamat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/azamat/32/6892_2.png) [@Azamat](https://discourse.julialang.org/u/Azamat)\
**Post date:** [May 16, 2019, 4:48pm UTC](https://discourse.julialang.org/t/graph-construction-performance/24288/1 "2019-05-16T16:48:08Z")

</div>

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

```nohighlight
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?

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [May 16, 2019, 5:06pm UTC](https://discourse.julialang.org/t/graph-construction-performance/24288/2 "2019-05-16T17:06:22Z")

</div>

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](http://juliagraphs.github.io/LightGraphs.jl/latest/generators.html#All-Generators-1) 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
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](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-array-1) 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](http://juliagraphs.github.io/LightGraphs.jl/latest/developing.html) 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.

---

<div class="post-metadata">

**Author:** ![Daniel\_Berge](https://avatars.discourse-cdn.com/v4/letter/d/eb9ed0/32.png) [@Daniel\_Berge](https://discourse.julialang.org/u/Daniel_Berge)\
**Post date:** [May 16, 2019, 6:15pm UTC](https://discourse.julialang.org/t/graph-construction-performance/24288/3 "2019-05-16T18:15:15Z")

</div>

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.