TreeD : A Library for Tree Decomposition

 

Source Code

 

TreeD is a C++ library for tree decomposition methods. At present treed contains implementations of three popular heuritics for tree decomposition, and optimal methods for hypertree decomposition and connected hypertree decomposition. The three heuristics in treed are: maximum-cardinality search, minimum-degree and minimum fill-in.

All the implemented decomposition methods take a hypergraph as input in the HG-format specified here, and the output is either a tree decomposition or a hypertree decomposition.

Apart from implementing the decomposition methods, the library also has functions to export the input HG-format files into the graph format used by the QuickBB tool or the format used by HTDECOMP tool.

The following sections specify the organization of the files in the zip-archive distributed above, and then give hints about some of the examples distributed in the archive.

 

Organization

The files in the distributed zip-archive belong to four categories: source-files, example-tools, instance-files and miscellaneous.

-Source-files: The source files are those in the directory "./src". This directory contains the C++ source code for the classes implementing the decomposition methods and the small utilities like file-format convertors.

-Example-files: The example files are those in the directory "./examples". Each sub-directory of "./examples" contains an example tool implemented using the source files. The example tools specify how to use the library while creating tools using it.

-Instance-files: Each one the instance files contain data of either a hypergraph in HG-format or a graph in the input format of the QuickBB tool or in the hypergraph format used by the HTDECOMP tool. The instance files are at present scattered in different directories, but mostly in the "./instances" directory. The "./bench" directory contains the instances used in the experiments of the IJCAI-2007 paper listed in the related-articles section below.

-Miscellaneous: There are miscellaneous files scattered in different places of the archive, and they are like scripts and data-files, used during some experiments.

 

Source Directory

As mentioned above, all the source files of the library are located in the "./src" directory. To compile the source files just use the make command in the directory.

 

Examples Directory

As mentioned above, all the example tools using the library are located in the "./examples" directory.

Before compiling any example tool, the source files should have been compiled as specified above. To compile an example tool, just use the make command in the sub-directory corresponding to the tool. Executing the example tools without parameters will print the usage hints.

Some of the important example tools are:

-treed: An important example tool is the treed tool located in the directory "./examples/treed" which takes a hypergraph and some parameters as input. The input parameters can be used to choose a decomposition method, and the output of the tool will be the width of the resulting decomposition. The treed tool could be used to check the width of decompositions resulting from one of the three popular heuristics on input hypergraphs.

-htd: This example tool takes a hypergraph and width (w) as input and specifies whether a connected-hypertree decomposition of width at most "w" is possible. Optionally, a time limit can be specified to the tool.

-opthtd: This example tool takes a hypergraph as input and returns the optimal connected hypertree decomposition width. The optimal width is obtained by the a sequence of queries corresponding to the decision version of the optimal connected hypertree decomposition problem, as mentioned in the experiments section of the IJCAI-2007 paper listed below in the related-articles section.

-normalhtd: This example tool takes a hypergraph and width (w) as input and specifies whether a hypertree decomposition of width at most "w" is possible. Optionally, a time limit can be specified to the tool. Note: the htd tool, mentioned above, is for connected-hypertree decomposition, while the normalhtd is for hypertree decomposition.

-normalopthtd: The functionality of this tool is just as the above opthtd tool, except that the normalopthtd tools is for finding optimal hypertree decomposition, while the opthtd is for finding optimal connected-hypertree decomposition.

-egraph: This tool takes a hypergraph in HG-format as input and dumps the corresponding graph in the format used by the QuickBB tool.

-exportdbai: This tool takes a hypergraph in HG-format as input and dumps the corresponding graph in the format used by the HTDECOMP tool.

 

Related Articles

The following articles used the treed library in the experiments:


[1]. Sathiamoorthy Subbarayan and Henrik Reif Andersen, "Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs", IJCAI 2007, Hyderabad, pp 180-185.
[2]. Sathiamoorthy Subbarayan, "An Empirical Comparison of CSP Decomposition Methods", Doctoral Program, CP 2007, Providence.

 

Related Online Links
Connected-hypertree Decomposition tool binary along with description of HG-format
Optkdecomp tool by Francesco Scarcello
Optkdecomp and Redkdecomp tools by Peter Harvey
HTDECOMP tool with several heuristics for hypertree decomposition
QuickBB tool, along with source code, by Vibhav Gogate for tree decomposition
Tree-of-BDDs compiler built using TreeD


For comments and suggestions please email me :

Sathiamoorthy Subbarayan, 20.July.2007