BoundedDegreeGraphs

This package provides simple graph types which do preallocate data such that the operations add_edge!, rem_edge!, has_edge are in-place for bounded degree graphs (also called uniformly sparse graphs).

• The preallocated memory is of size $\mathcal{O}( \Vert G \Vert \mathrm{deg}(G) )$. If the degree is exeeded, then the type might occasionally allocate, but still works.
• The operations has_edge, add_edge and rem_edge take $\mathcal{O}( \mathrm{deg}(G) )$ time, since it required to iterate a list of size $\mathrm{deg}(G)$.
• In the simple test case below, the speed-up compared to SimpleGraph is by a factor $\times 2$. Speedup holds only for small degrees!

Application in agent-based modelling

The original application is for biological modelling of cell migration, where one has to dynamically create and destroy adhesive contacts between cells. Due to geometric constraints the resulting graph is of bounded degree.

Usage

The type implements the interface outlined in Graphs.jl - Developing Alternate Graph Types. To use the packge, one should include Graphs.jl, i.e.

using Graphs
using BoundedDegreeGraphs

The two main constructors are

BoundedDegreeDiGraph( n_nodes, degree)

for a directional graph with n_nodes and pre-allocated lists for bounded graphs of degree degree. It is no problem to exeed degree, however, in that case some allocations might occur.

For undirected graphs, one can use

BoundedDegreeGraph( n_nodes, degree)

Metadata for vertices and edges is also supported, with the types

n_nodes = 10
degree = 4 
edge_default = Inf64 
vertex_default = (x = 0.0, y = 0.0)
g = BoundedDegreeMetaDiGraph(n_nodes, degree, edge_default, vertex_default) 

where edge_default is the value assigned to edges if an edge is created without providing some data. Similar, vertex_default is the default (and inital) value for all vertices.

For adding new vertices and edges with metadata, use the corresponding functions with added argument:

add_edge!(g, 1, 2)
g[1, 2] == Inf64 
add_edge!(g, 1, 3, 1.0)
g[1, 3] == 1.0
g[1, 3] = 10.0  # overwriting meta data

add_vertex!(g, (x = 1.0, y = 0.0))
g[11] == (x = 1.0, y = 0.0)
g[11] = (x = 1.1, y = 0.1)  # overwriting meta data

The same interface works for undirected graphs with metadata, using the constructor

g = BoundedDegreeMetaGraph(n_nodes, degree, edge_default, vertex_default) 

Example

using Graphs, BoundedDegreeGraphs

# testing for allocations
function test_allocations(g, edges, add, rem)
    for i in edges, j in add
        add_edge!(g, i, j)
    end

    for i in edges, j in rem 
        has_edge(g, i, j)
    end

    for i in edges, j in rem
        rem_edge!(g, i, j)
    end
end


degree = 20
g = BoundedDegreeDiGraph(1000, degree)
test_allocations(g, 1:1000, 1:20, 11:30)  # warm start

g = BoundedDegreeDiGraph(1000, 20)
@time test_allocations(g, 1:1000, 1:20, 11:30)  
# 0.001040 seconds

g = SimpleDiGraph(1000)
@time test_allocations(g, 1:1000, 1:20, 11:30)

g = SimpleDiGraph(1000) 
@time test_allocations(g, 1:1000, 1:20, 11:30)  
# 0.001930 seconds (2.10 k allocations: 842.188 KiB)

#=
# This is not a timing artefact. The difference is still there with BenchmarkTools:
using BenchmarkTools
@btime test_allocations(g, 1:1000, 1:20, 11:30) setup = (g = BoundedDegreeDiGraph(1000, 20)) 
# 379.292 μs (0 allocations: 0 bytes)

@btime test_allocations(g, 1:1000, 1:20, 11:30) setup = (g = SimpleDiGraph(1000)) 
# 710.905 μs (2100 allocations: 842.19 KiB)
=#

Internal representation

Internally, the adjacent vertices for each vertex i are stored in a Vector{Int64} which has zeros at unoccupied places. Each time a new vertex is added, one of the free spots will be used. If no free spots are left, then push!(adj, j) is used to add new edges (which will allocate occasionally).