Many graph algorithms can be sped up be working with tree decompositions of graphs. These are generalized by structured decompositions, which can be formed for arbitary data structures. StructuredDecompositions.jl is a package for manupulating and working with structured decompositions. It is part of the AlgebraicJulia ecosystem.
Since the definition of a structured decompositions is functorial, one can easily lift computational problems (defined as functors mapping inputs to solution spaces) to functors between from decompositions of the inputs to decompositions of solution spaces. This package allows one to leverage insights to solve decision problems that are encoded as sheaves efficiently (i.e. in fixed-parameter-tractable time parameterized by the width of the decompositions).
You can benchmark StructuredDecompositions by navigating to the project directory, running Julia, and typing the following into the REPL.
using Pkg
Pkg.activate("benchmark")
Pkg.instantiate()
using PkgBenchmark
using StructuredDecompositions
benchmarkpkg(StructuredDecompositions)