# \[ANN\] BoundedDegreeGraphs.jl
**URL:** https://discourse.julialang.org/t/ann-boundeddegreegraphs-jl/99615
**Category:** Package Announcements
**Tags:** graphs
**Created:** [May 30, 2023, 4:16pm UTC](https://discourse.julialang.org/t/ann-boundeddegreegraphs-jl/99615 "2023-05-30T16:16:19Z")
**Posts on this page:** 3
**Page:** 1
### Author:  [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)
#### Post date: [May 30, 2023, 4:16pm UTC](https://discourse.julialang.org/t/ann-boundeddegreegraphs-jl/99615/1 "2023-05-30T16:16:20Z")
This is a very small package with a specific aim:
> **An allocation-free graph type** for graphs that have a **small (\< 30) bounded degree**!
## To keep it short:
- The operations `add_edge!`, `rem_edge!`, `has_edge` are allocations-free 📥 if the degree stays within bounds.
- It can be up to 2 \times faster than `SimpleGraph`;
- however, that highly depends on the degree and the task!
- As a rule of thumb, most operations take \mathcal{O}( d ) time where d is the degree bound.
- There are types for: Directional, undirectional graphs with metadata per edge, and metadata per vertex. The corresponding type names are `BoundedDegree{Meta}{Di}Graph`. (Long, explicit and ugly 😬)
- Memory footprint is \approx \vert G \vert \cdot d where d is the degree bound.
An extreme example: Imagine `test_allocation` adds for each vertex `20` edges, checks `20` times if an edge exists and removes `20` edges:
```julia
using BenchmarkTools, BoundedDegreeGraph, Graphs
@btime test_allocations(g, 1:1000, 1:20, 11:30) setup = (g = SimpleDiGraph(1000))
# 710.905 μs (2100 allocations: 842.19 KiB)
d = 20
@btime test_allocations(g, 1:1000, 1:20, 11:30) setup = (g = BoundedDegreeDiGraph(1000, d))
# 379.292 μs (0 allocations: 0 bytes)
```
[Link to full example](https://github.com/SteffenPL/BoundedDegreeGraphs.jl#example)
## How to use it:
The graph types implement the Graphs.jl interface with only minor adaptation for metatypes. Check out the [readme](https://github.com/SteffenPL/BoundedDegreeGraphs.jl).
## Typical application:
I wrote the package with spatial graphs in mind. In particular, for applications in **contact mechanical simulations** or **agent-based modeling**. This package might be interesting (or already solved by) @Datseris?
For agent-based models, one maybe has a dynamic graph of interacting agents. Such graphs have often a very small bounded degree since non-overlapping objects like spheres can only have a limited amount of neighbors. The `BoundedDegreeGraph` types are well-suited to keep track of such interactions, and they avoid unwanted allocations.
## Internal design:
For each vertex `i` , the corresponding edges are stored in a `Vector{Int64}` which is initially `adj_i = zeros(d)`. Each zero represents an unused slot. To add an edge `(i,j)`, we search for the first zero in `adj_i` and then write `j` into that position.
## Limited scope:
Note that the default `SimpleGraph` type from Graphs.jl is better for the majority of applications! Maybe even for many agent-based models 😉
* * *
_In three days, it will be my first registered Julia package 😊 🎉_
Thanks for @gdalle for your feedback and help!
> **[GitHub - SteffenPL/BoundedDegreeGraphs.jl: Allocation free graph implementation for sparse...](https://github.com/SteffenPL/BoundedDegreeGraphs.jl)**
>
> Allocation free graph implementation for sparse graphs with bounded degree.
---
### Author:  [@kellertuer](https://discourse.julialang.org/u/kellertuer)
#### Post date: [May 30, 2023, 8:52pm UTC](https://discourse.julialang.org/t/ann-boundeddegreegraphs-jl/99615/2 "2023-05-30T20:52:31Z")
Congratulations on our first package! 🥳
While I personally currently do not yet see, where _I_ could use it, I am sure this speedup is useful for many users with large, but degree wise sparse graphs!
One thing you could maybe do over time, is to document the types you export and maybe also your internal structures and functions?
I feel doc strings are very often useful for other people using this package.
_edit:_ also looked at the second thing I usually ask about, your testcoverageof 88% looks quite good already 🙂
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [May 30, 2023, 9:36pm UTC](https://discourse.julialang.org/t/ann-boundeddegreegraphs-jl/99615/3 "2023-05-30T21:36:42Z")
Would it make sense to use mutable StaticArrays for the adjacency lists of each vertex, if the maximum degree is known statically?