pymeiji 1.0.0

A simple jpype-based python wrapper around Hisao Tamaki's treewidth solver for PACE 2017

This is a simple python wrapper around https://github.com/TCS-Meiji/PACE2017-TrackA# (meiji treewidth solver from PACE 2017), based on jpype. The original implementation of the solver is in java. The algorithm is described in https://arxiv.org/abs/1704.05286.

Installation instructions

pip install pymeiji

Usage

def meiji_solver(edge_list):
    """
        Exact computation of the treewidth of a graph.

        Python-wrapper around the PACE 2017 meiji solver,
        which was originally written in java,
        and whose details are described in
        https://arxiv.org/abs/1704.05286

        Parameters
        ----------
            edge_list: list of tuples of integers 
                list of edges of the graph. Each edge must
                be a tuple of 2 integers (u,v).
                The integers should range from 0 to
                the number of vertices in the graph - 1.

        Returns
        -------
        (treewidth, bags, bag_adj)
            A tuple consisting of three objects.  The first is an integer equal
            to the treewidth.  The second is a python dictionary associating
            integers (bag index) to lists of integers (bag content). The 
            third is also a dictionary, associating integers (bag index)
            to lists of integers (indices of the neighbors of that bag
            in the tree decomposition).
    """

>>> from pymeiji import meiji_solver
>>> meiji_solver([(0,1),(1,2),(2,3),(0,3)])
(2, {1: [0, 1, 3], 2: [1, 2, 3]}, {1: [2], 2: [1]})