This is a very small package with a specific aim:

An allocation-free graph typefor graphs that have asmall (< 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:

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

## How to use it:

The graph types implement the Graphs.jl interface with only minor adaptation for metatypes. Check out the readme.

## 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!