treedec

treedec provides tree decomposition algorithms.

A tree decomposition of a simple, loopless, undirected graph G is a tree T with bags at its nodes containing vertices from G. The usual conditions apply. By convention, a tree is an acyclic graph with exactly one connected component. The bagsize of T is the size of the biggest bag, which is a notion for the (width of T) + 1.

There is work in progress, so this description should be understood as normative. Deviations from conventions stated here are considered bugs.

Prerequisites

• boost (tested with >=1.62)
• a C++ compiler with support for c++11.

Optional:

• Python/Cython (disable with --without-python)
• gala headers; will be detected, if available, by configure (need libboost_graph in that case)

Build process

The treedec package uses an autotools based build system. See INSTALL for generic intructions.

For developpers and git users, the bootstrap script will create the necessary files. After cloning the repository, type

$ cd $repository_root # <= the directory containing this README file. $ ./bootstrap

Developpers are advised to build in a separate directory. For this, change to a new empty directory and run

$ path_to_repository/configure [flags].

Build process (python)

There is a build system for pure python environments, see python/README.

The interface

A tree decomposition algorithm is a class template

template<class G, template<class G_, class ...> class C>
class ALGORITHM{
[..]
};

where G is a graph and C is a config object. A graph is expected to come with a boost graph interface. There are some extra implicit assumptions, which the graph data structure may or may not enforce.

An algorithm has (should have) a constructor taking G& and a constructor taking const G&. You should expect the argument to be modified, unless it's const, i.e. make sure to cast to const reference, if this is not desired.

An algorithm also provides

T get_tree_decomposition() const;
template<class TT>
void get_tree_decomposition(TT&) const;

which is meant to work with treedecomposition types (see below).

In namespace treedec we currently have (needs verification)

prep::*        // preprocessing
he::fill_in    // fillIn heuristic
he::min_degree // minDegree heuristic
he::thorup     // thorups heuristic
ex::ta         // tamakis algorithm
    TR         // tamakis exact PID (without preproc)
ex::cutset     // exact algorithm
comb::PP_FI    // preprocessing + fill_in
comb::PP_FI_TM // preprocessing + fill_in + triangulation
comb::ex17     // PACE 17 exact (pp + tamaki)

Graph types

A graph is expected to be a model of AdjacencyGraph, but without self loops and without parallel edges. It needs to be undirected. Some algorithms support graphs that model BidirectionalGraph. These graphs must not contain more than one edge for any two vertices, as accessed through boost::edges.

Configuration objects

Config objects can control some of the algorithm behaviour, such as

• statistics generation,
• debug output,
• signalling,
• selection of subalgorithm, subroutine and data structure.

The default, algo::cfg_default, is a sensible choice, if you don't care.

(TODO: more on config objects)

Tree decompositions

A tree decomposition is an undirected graph in the above sense with a vertex property of access type treedec::bag_t. Sometimes bidirectional graphs also work. In that case, the edges of the tree decomposition must be oriented away from a root vertex.

The expected models are

#include <treedec/treedec_traits.hpp>
typedef std::vector<vertex_descriptor> bag_container_type;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
        boost::property<treedec::bag_t, bag_container_type> > T;

or

typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS,
        boost::property<treedec::bag_t, bag_container_type> > T;

where vertex_descriptor must be compatible with the graph to be decomposed.

It is possible to use custom tree decomposition types, such as with bundled properties. If you have a graph

struct mybundle{
   std::set<unsigned> bag; // must be "bag" right now.
   [..]
};
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
                              mybundle> my_td_type;

you can make bags accessible from treedec using

TREEDEC_TREEDEC_BAG_TRAITS(my_td_type, bag);

tdecomp

An example driver. Reads in .gr files (PACE style) and ejects .td. Supports several algorithms. These can be switched on individually, using options such as --pp, --fi, --ppfi, --ex17. Selected algorithms run in parallel, some heuristics permit interruption using a TERM signal. In the interrupted case, the best currently known decomposition is printed.

Example:

$ tdecomp --fi < my_graph.gr > my_decomposition.td
$ td-validate my_graph.gr my_decomposition.td