# Is there a allocation free graph package?

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}
data::Array{T,2}
end

data = fill(default_data, n, max_adj)
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)

``````
3 Likes

Hi, Graphs.jl maintainer here! I’m not aware of any such package but you’re welcome to contribute one If you need any help setting it up, let me know

2 Likes

Thank you for the reply!

Sure, I’m happy to make it. I guess a small package/module which is compatible with Developer Notes · Graphs.jl would be best? Or is there some place where a PR would fit?

1 Like

I think a small package compatible with the interface you pointed out would be ideal!

2 Likes

I created this small package GitHub - SteffenPL/BoundedDegreeGraphs.jl

It supports directed and undirected graphs `BoundedDegreeDiGraph, BoundedDegreeGraph` and doesn’t allocated for adding, removing edges and `has_edge`. (Actually, I think it doesn’t allocated for most operations, including iteration. However, I haven’t checked it yet.)

It’s not registered yet (it’s my first package actually…).

Any feedback is very welcome. I will maybe register and announce it, once I added support for weights or metadata (using the same approach as for edges applied to the data).

• Speed-up compared to `SimpleDiGraph` is not too much (maybe `x1.5` times faster, but depends highly on benchmark).
• Exceeding the degree is no problem, it just allocates then.
• Initial memory allocated is `n_nodes * degree_bound * sizeof(IndexType)`.
4 Likes

I’ll take a look sometime next week (I’m on vacation this week). Feel free to ping me if I forget!

1 Like

No rush and enjoy your vacation!

@gdalle a friendly ping

[but again, no rush… In the meantime, I added support for metadata.]

Woops! I have 10h of train tomorrow, so I’ll try to take a look

1 Like