incidence_benchmark.md

using LightGraphs

function incidence_matrix_edges(g::SimpleGraph, T::DataType=Int)
    n_v = nv(g)
    n_e = ne(g)
    nz = 2 * n_e

    # every col has the same 2 entries
    u_coef = is_directed(g)? -one(T) : one(T)
    v_coef = one(T)
    colpt = collect(1:2:(nz + 1))
    nzval = repmat([u_coef, v_coef], n_e)

    # iterate over edges for row indices
    rowval = zeros(Int, nz)
    for (i,e) in enumerate(edges(g))
        rowval[2*i - 1] = src(e)
        rowval[2*i] = dst(e)
    end

    spmx = SparseMatrixCSC(n_v,n_e,colpt,rowval,nzval)
    return spmx
end

incidence_matrix_edges (generic function with 2 methods)

function incidence_matrix_fadj(g::SimpleGraph, T::DataType=Int)
    n_v = nv(g)
    n_e = ne(g)
    nz = 2 * n_e

    # every col has the same 2 entries
    u_coef = is_directed(g)? -one(T) : one(T)
    v_coef = one(T)
    colpt = collect(1:2:(nz + 1))
    nzval = repmat([u_coef, v_coef], n_e)

    # iterate over edges for row indices
    rowval = zeros(Int, nz)
    i = 1
    for u in vertices(g)
        for v in out_neighbors(g, u)
            if u < v
                rowval[2*i - 1] = u
                rowval[2*i] = v
                i += 1
            end
        end
    end

    spmx = SparseMatrixCSC(n_v,n_e,colpt,rowval,nzval)
    return spmx
end

incidence_matrix_fadj (generic function with 2 methods)

for k in 1:10
    n = k * 100000
    m = 2*n
    g = erdos_renyi(n, m)
    println("$n, $m")
    @time incidence_matrix_edges(g);
    @time incidence_matrix_fadj(g);
end

100000, 200000
  0.029900 seconds (400.02 k allocations: 19.837 MB, 9.53% gc time)
  0.011978 seconds (12 allocations: 7.630 MB)
200000, 400000
  0.062988 seconds (800.02 k allocations: 39.673 MB, 8.67% gc time)
  0.026966 seconds (12 allocations: 15.259 MB, 9.26% gc time)
300000, 600000
  0.085479 seconds (1.20 M allocations: 59.510 MB, 4.87% gc time)
  0.037151 seconds (12 allocations: 22.889 MB, 7.09% gc time)
400000, 800000
  0.123914 seconds (1.60 M allocations: 79.346 MB, 5.56% gc time)
  0.054212 seconds (12 allocations: 30.518 MB, 3.20% gc time)
500000, 1000000
  0.158351 seconds (2.00 M allocations: 99.183 MB, 6.08% gc time)
  0.065826 seconds (12 allocations: 38.147 MB, 6.15% gc time)
600000, 1200000
  0.328696 seconds (2.40 M allocations: 119.019 MB, 45.13% gc time)
  0.078158 seconds (12 allocations: 45.777 MB, 3.66% gc time)
700000, 1400000
  0.373240 seconds (2.80 M allocations: 138.855 MB, 42.76% gc time)
  0.093220 seconds (12 allocations: 53.406 MB, 4.35% gc time)
800000, 1600000
  0.432465 seconds (3.20 M allocations: 158.692 MB, 41.68% gc time)
  0.110367 seconds (12 allocations: 61.036 MB, 4.45% gc time)
900000, 1800000
  0.485096 seconds (3.60 M allocations: 178.528 MB, 42.06% gc time)
  0.119374 seconds (12 allocations: 68.665 MB, 2.03% gc time)
1000000, 2000000
  0.550311 seconds (4.00 M allocations: 198.365 MB, 41.41% gc time)
  0.138712 seconds (12 allocations: 76.294 MB, 6.03% gc time)