Slow construction of SymmetricGraph.

[samuelsonric]

Consider the following two functions, which construct an undirected graph from a collection of edges.

using BenchmarkTools
using Catlab
using Graphs

function make_graph_1(n, edges)
    graph = Catlab.Graphs.SymmetricGraph(n)
    for (v₁, v₂) in edges
        if !Catlab.Graphs.has_edge(graph, v₁, v₂)
            Catlab.Graphs.add_edge!(graph, v₁, v₂)
        end
    end
    graph
end

function make_graph_2(n, edges)
    graph = Graphs.Graph(n)
    for (v₁, v₂) in edges
        if !Graphs.has_edge(graph, v₁, v₂)
            Graphs.add_edge!(graph, v₁, v₂)
        end
    end
    graph
end

n = 1000
edges = zip(1:n-1, 2:n)

Then @benchmark make_graph_1(n, edges) outputs

BenchmarkTools.Trial: 427 samples with 1 evaluation.
 Range (min … max):  10.694 ms …  16.823 ms  ┊ GC (min … max): 0.00% … 10.04%
 Time  (median):     11.526 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   11.708 ms ± 790.291 μs  ┊ GC (mean ± σ):  3.23% ±  5.15%

      ▁ ▃▆▁ ▁       ▇█▅▂
  ▂▂▄▃█████▆█▆▆▅▅▅▅▆████▇▃▄▄▁▃▁▁▁▁▁▁▁▃▁▂▂▃▅▄▅▄▂▄▃▄▂▃▂▃▃▄▅▅▆▅▄▅ ▄
  10.7 ms         Histogram: frequency by time         13.3 ms <

 Memory estimate: 10.71 MiB, allocs estimate: 131834.

whereas @benchmark make_graph_2(n, edges) outputs

BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  48.125 μs …  1.879 ms  ┊ GC (min … max): 0.00% … 95.21%
 Time  (median):     59.875 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   65.047 μs ± 93.556 μs  ┊ GC (mean ± σ):  8.12% ±  5.44%

                    ▁▃▅▂    ▁▅█▇▄
  ▂▂▁▁▂▂▁▁▂▂▂▂▂▃▅▆▅▅██████▇███████▆▅▄▄▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂ ▄
  48.1 μs         Histogram: frequency by time        74.2 μs <

 Memory estimate: 148.59 KiB, allocs estimate: 2002.