I’m dealing with graphs that have a maximal adjacency count. In that setting, it is possible to add, iterate and remove edges without allocations (see implementation below). That is important since I need to do these operations very often for a graph with up to millions of entries.
Question: I wanted to ask if there is already a package for graphs without allocations?
(I prefer to use other people’s work 
)
Quick example implementation:
struct MaxAdjGraph{T}
ith_adjs::Array{Int64,2}
data::Array{T,2}
end
function MaxAdjGraph(n::Int64, max_adj::Int64, default_data = missing)
ith_adjs = zeros(Int64, n, max_adj)
data = fill(default_data, n, max_adj)
return MaxAdjGraph(ith_adjs, data)
end
function location(g::MaxAdjGraph, i::Int64, choices)
for k in axes(g.ith_adjs, 2)
if g.ith_adjs[i, k] in choices
return k
end
end
return 0
end
function add_edge!(g::MaxAdjGraph, i::Int64, j::Int64, data::T = missing) where {T}
k = location(g, i, (0, j))
if k <= 0
error("Too many edges for node $(i) in graph $(g).")
end
g.ith_adjs[i, k] = j
g.data[i, k] = data
end
function delete_edge!(g::MaxAdjGraph, i::Int64, j::Int64)
k = location(g, i, (j,))
if k > 0
g.ith_adjs[i, k] = 0
end
end
has_edge(g::MaxAdjGraph, i::Int64, j::Int64) = location(g, i, (j,)) > 0
Base.getindex(g::MaxAdjGraph, i::Int64, j::Int64) = g.data[i, location(g, i, (j,))]
g = MaxAdjGraph(10, 3, 0.0)
add_edge!(g, 1, 2, 2.0)
g[1,2]
has_edge(g, 1, 2)
delete_edge!(g, 1, 2)
has_edge(g, 1, 2)
If you need any help setting it up, let me know