README
¶
BalancedGo
Compute Generalized Hypertree Decompositions via the use of balanced separators, in Go with a focus on parallelism.
Takes as input a hypergraph in HyperBench format or PACE Challenge 2019 format, and a width parameter (positive non-zero integer). HyperBench is a benchmark library, containing over 3000 hypergraphs from CQ and CSP instances, from industry and research.
Installation
Needs Go >= 1.12, look here for Linux, MacOS or Windows versions.
Simply run make, alternatively on platforms without the make tool, run go build
Usage
No fixed command-line interface. Use "BalancedGo -h" to see the currently supported commands. Generally, any run will require 1) a valid hypergraph, according to the formats specified above, 2) a specified width (unless the "exact" or "approx" flags are used) and 3) an algorithm to actually compute an HD or GHD (depending on the type of algorithm).
Documentation
¶
Overview ¶
BalancedGo - A research prototype to compute structural decompositions of Conjunctive Queries and CSPs via the use of Balanced Separators with a focus on parallelism using the programming language Go.
For more detailed information, see "Fast and Parallel Decomposition of Constraint Satisfaction Problems", Georg Gottlob, Cem Okulmus, Reinhard Pichler, released in Proc. IJCAI 2020. https://www.ijcai.org/Proceedings/2020/161
The tool is split into three packages. main is responsible to actually run the various algorithms supported by the tool, lib is used to implement various functionality used by the algorithms and lastly algorithms which implements the actual algorithms to compute various decompositions.
In addition to this, there is also a tool subdirectory in the repository which is intended to support functionality not directly related to the computation of decompositions, such as changing the formatting of hypergraphs, or fixing a faulty decomposition.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package algorithms implements various algorithms to compute Generalized Hypertree Decompositions as well as the more restricted set of Hypertree Decompositions.
|
Package algorithms implements various algorithms to compute Generalized Hypertree Decompositions as well as the more restricted set of Hypertree Decompositions. |
|
Package lib provides various functions, data structures and methods to aid in the design of algorithms to compute structural decomposition methods.
|
Package lib provides various functions, data structures and methods to aid in the design of algorithms to compute structural decomposition methods. |