[ANN] BoundedDegreeGraphs.jl

Package Announcements
1

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 :inbox_tray: 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 :grimacing:)
  • 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)

Link to full example

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 :wink:

In three days, it will be my first registered Julia package :blush: :tada:

Thanks for @gdalle for your feedback and help!

8 Likes
2

Congratulations on our first package! :partying_face:

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

2 Likes
3

Would it make sense to use mutable StaticArrays for the adjacency lists of each vertex, if the maximum degree is known statically?

2 Likes