treedecomp

TreeDecomp

TreeDecomp is a simple python package for storing and manipulating tree decompositions. It was originally written as part of infrared, a generic C++/Python hybrid library for efficient (fixed-parameter tractable) Boltzmann sampling. By default, TreeDecomp runs treewidth_min_fill_in from networkx $20$ times on randomized input and returns the one with the smallest treewidth as treedecomp.TreeDecomposition.

Simple Usage

The class TreeDecompositionFactory creates a tree decomposition for a given hypergraph. The result is stored in TreeDecomposition. A hypergraph is a pair of integer and a list of lists, where the former one is the number of nodes and the later one is the list of hyperedges.

>>> import treedecomp as td
>>> nb_nodes = 6
>>> hyperedges = [[0,1,5], [2,4], [2,5], [3,4,5]]
>>> tree = treedecomp.TreeDecompositionFactory().create(nb_nodes, hyperedges)
>>> tree.get_bags()
[[4, 5, 3], [4, 5, 2], [5, 1], [5, 0, 1]]
>>> tree.get_edges()
[(0, 1), (0, 2), (2, 3)]
>>> tree.toposorted_bag_indices()
[0, 2, 3, 1]
>>> with open('tree.dot', 'w') as output:
...     td.writeTD(output)

Future Work

One can notice TreeDecomp offers two other tree decompoistion factories HTDTreeDecompositionFactory and TDLibTreeDecompositionFactory. These two are for supporting tree decompoitions using libhtd (via python wrapper) or calling TDlib (written in java) that will be included in the future