Skip to main content

Python Class for Tree Decomposition

Project description


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('', '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

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

treedecomp-1.1.0.tar.gz (20.5 kB view hashes)

Uploaded source

Built Distribution

treedecomp-1.1.0-py3-none-any.whl (19.8 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page