SHARP - A Smart Hypertree decomposition-based Algorithm fRamework for Parameterized problems
Contents
News
Release of SHARP 1.1.1
21.11.2013Version 1.1.1 of SHARP is now available (see Downloads). It features a new normalization option (weak normalization) and optionally adds an empty root or empty leaves to the decomposition.
TopRelease of SHARP 1.1
23.09.2013Version 1.1 of SHARP is now available (see Downloads). It includes some bugfixes and functions for greater convenience.
TopRelease of SHARP 1.0
16.05.2011SHARP has hit stable and has now been released as version 1.0 (see Downloads)
TopDocumentation
SHARP is a framework that enables rapid development of algorithms that are based on tree or hypertree decompositions. Classically, such algorithms perform a bottom-up evaluation of the (hyper-)tree, where at each node the possible partial solutions are calculated, and at the root node, one arrives at the actual solution to the original problem. If the (hyper-)tree decomposition is normalized, there are only four different node types and thus only four basic operations for each node type have to be implemented. The framework provides (hyper-)tree decomposition routines and algorithm interfaces that only require the implementation of the four aforementioned operations plus input parsing in order to get a running algorithm. All object and data management that is required to e.g. traverse the tree is handled by the framework using algorithm-independent code.
The documentation for the framework is available here.
TopDownloads
The SHARP source code is available under the open-source GPLv3 license.
Run the usual ./configure && make && sudo make install to compile and install.
- SHARP 1.1.1 source code (gnu-zipped tar archive)
- SHARP 1.1 source code (gnu-zipped tar archive)
- SHARP 1.0 source code (gnu-zipped tar archive)
In order to compile the library, the GNU Multiple Precision Arithmetic Library
(GMP - available here) should be available on your system. If you want to compile the code
without this, you can add the --without-gmp option when calling the ./configure script. In this case,
the GMP library is not needed, however only 64bit integers are used for counting, as opposed to arbitrary precision integers.
Projects
The SHARP library is currently being used in the following projects that we know of:
- dynASP - A dynamic programming-based answer set programming solver.
- dynPARTIX - A dynamic programming argumentation reasoning tool.
- D-FLAT: Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving.
Note that the above list may be and probably is incomplete.
Top