# Is there a allocation free graph package?

**URL:** <https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327>\
**Category:** Graphs\
**Tags:** graphs\
**Created:** [April 11, 2023, 5:10am UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327 "2023-04-11T05:10:21Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [April 11, 2023, 5:10am UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/1 "2023-04-11T05:10:21Z")

</div>

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:

> ****
>
> ```julia
> 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)
> 
> ```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 11, 2023, 6:30am UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/2 "2023-04-11T06:30:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [April 11, 2023, 6:52am UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/3 "2023-04-11T06:52:19Z")

</div>

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](https://docs.juliahub.com/Graphs/VJ6vx/1.5.0/developing/#Developing-Alternate-Graph-Types) would be best? Or is there some place where a PR would fit?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 11, 2023, 7:42am UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/4 "2023-04-11T07:42:59Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [April 11, 2023, 12:47pm UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/5 "2023-04-11T12:47:53Z")

</div>

I created this small package [GitHub - SteffenPL/BoundedDegreeGraphs.jl](https://github.com/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)`.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 11, 2023, 8:33pm UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/6 "2023-04-11T20:33:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [April 11, 2023, 10:19pm UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/7 "2023-04-11T22:19:00Z")

</div>

No rush and enjoy your vacation! ☀

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [April 24, 2023, 6:50am UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/8 "2023-04-24T06:50:01Z")

</div>

@gdalle a friendly ping 🙂

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

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 24, 2023, 7:07am UTC](https://discourse.julialang.org/t/is-there-a-allocation-free-graph-package/97327/9 "2023-04-24T07:07:28Z")

</div>

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