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 :smiley: )


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)

3 Likes

Hi, Graphs.jl maintainer here! I’m not aware of any such package but you’re welcome to contribute one :slight_smile: 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! :sunny:

@gdalle a friendly ping :slight_smile:

[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 :slight_smile:

1 Like