This program computes the Tutte polynomial of a user-supplied graph using the algorithm described in:
Bedini, A. & Jacobsen, J.L. A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings. J. Phys. A: Math. Theor. 43, 385001 (2010). dx.doi.org/10.1088/1751-8113/43/38/385001.
A modern C++ compiler which supports C++11.
Boost libraries, http://www.boost.org
Compilation and installation
$ git clone git://github.com/andreabedini/tutte.git $ cd tutte $ mkdir build $ cd build $ cmake .. $ make
You can also run some tests to make sure everything is working properly.
$ make test
Optionally, you can install the executable program to your path.
$ make install
The input is expected to be passed to the program through the standard input. The result will be printed to the standard output while any additional message will be printed on the standard error stream.
E.g. you can do
$ cat my_graph | bin/tutte
$ bin/tutte < my_graph
The input format looks like this:
This describe a graph with 8 vertices and 8 edges. Each edge is represented as a pair of numbers each representing a vertex.
It is important that the vertex numbering starts from zero, so that vertex indices are in [0..V) where V is the number of vertices.
Alternatively an input file can be specified with the option --input-file
$ bin/tutte --input-file my_input
NOTE: The input graph has to be connected, giving as input a graph with multiple connected components will result in a run-time error. This can be easily solved but I haven't had the time to work on it yet. Drop a line on the bug report if you feel like helping out.
A list of options is available with the
Allowed options: -h [ --help ] Produce help message --input-file arg Read the graph from a file. --degree Use greedy degree algorithm [default]. --fill-in Use greedy fill-in algorithm. --local-degree Use 'local' greedy degree algorithm. --local-fill-in Use 'local' greedy fill-in algorithm. --elimination-order arg Specify a vertex elimination order. --print-tree Print tree decomposition. --tree-only Print tree decomposition and exit. -f [ --flow ] Compute the flow polynomial -c [ --chromatic ] Compute the chromatic polynomial --chinese-remainder Use the chinese remainder trick.
--chromatic tell the program to compute the
relevant specialization of the Tutte polynomial. In the variables (Q, v), passing
--flow sets v = -Q, while passing
--chromatic sets v = -1.
--fillin choose which algorithm has to be used to compute the tree decomposition. The algorithms Greedy Degree and Greedy Fill-In are described in
Bodlaender, H.L. & Koster, A.M.C.A. Treewidth computations I. Upper bounds. Information and Computation 208, 259–275 (2010). 10.1016/j.ic.2009.03.008.
The algorithms local greedy degree and local greedy fill-in algorithm are home-crafted modifications to the above to make them always output a path-decomposition.
A vertex elimination order (see Bodlaender & Koster (2010) for the terminology) can be specified on directly on the command line as a comma separated list of vertices.
Edges are assigned to bags as they appear in the elimination ordering. For the sake of generality and maintenance, problem specific optimizations, such as the pruning procedure described in Bedini & Jacobsen (2010), are not implemented.