A Modular Library for Computing Tree Decompositions
Jdrasil is a library to compute tree decompositions of simple, undirected graphs. It was developed for the first Parameterized Algorithms and Computational Experiments Challenge (PACE). It provides exact sequential and parallel, as well as heuristic, and approximation algorithms.
Jdrasil is build in a very modular fashion. This allows researchers to simply add new algorithms, heuristics, or preprocessing routines, which can then be combined in any way.
You can obtain the latest stable version of Jdrasil here. Use the manual for an overview of the features of Jdrasil, or browse the JavaDoc for some implementation details. You can also build the latest version of Jdrasil manually (see below).
Jdrasil uses Gradle as build tool. Thanks to the gradle wrapper, nothing extra has to be installed in order to install Jdrasil.
To build Jdrasil, simply invoke the gradle build script:
cd Jdrasil ./gradlew assemble
There is also a bat-file for windows systems. After the script is finished, an executable jar will be placed in:
The jar can be used as library or as standalone:
java −jar build/jars/Jdrasil.jar java −cp build/jars/Jdrasil.jar jdrasil.Exact java −cp build/jars/Jdrasil.jar jdrasil.Heuristic java −cp build/jars/Jdrasil.jar jdrasil.Approximation
Building Start Scripts
Jdrasil comes with PACE like starting scripts:
tw-approximation. They can be build with gradle:
./gradlew exact ./gradlew heuristic ./gradlew approximation
Use the scripts as defined on the (PACE) website:
./tw−exact −s 42 < myGraph.gr > myGraph.td ./tw−heuristic −s 42 < myHugeGraph.gr > myHugeGraph.td
Build the Documentation
Jdrasil comes with a manual and JavaDocs. To build the manual, an up-to-date LuaLaTeX installation is required:
./gradlew manual ./gradlew javadoc
The manual will be placed in
build/docs/manual/manual.pdf and the JavaDocs in
Build for PACE
Jdrasil provides a Gradle task that builds the PACE-version of Jdrasil. In particular, this will build Jdrasil and create the above mentioned start scripts.