Introduction
Tutte polynomials play an important role in graph theory, combinatorics, matroid theory, knot theory, and experimental physics. For example, the polynomials can be evaluated to find the number of spanning trees in a graph, the number of forests in a graph, the number of connected spanning subgraphs, the number of spanning subgraphs, and the number of acyclic orientations. In addition, Tutte polynomials specialise to chromatic polynomials, flow polynomials, Jones polynomials for alternating links, and partition functions of the q-state Potts model from statistical physics.
While Tutte polynomials have many applications, there are few practical algorithms available for computing them for graphs of sufficient size. Prof. Gary Haggard has paved the way by developing the most efficient algorithm currently available for this, based on his earlier work on computing Chromatic Polynomials. The algorithm relies on various optimisations and heuristics to obtain good performance.
In these pages, you can find an implementation of Gary's algorithm in C++ developed by myself and Gary. We hope that this code may be useful to the algorithms community and that it will eventually lead to an efficient method for computing the Tutte polynomials of large graphs.
Publications
We are currently on a paper describing the algorithms used in this code; we have also developed a visualisation for the computation to aid in understanding it. Details of these papers are:
Computing Tutte Polynomials. Gary Haggard, David J. Pearce and Gordon Royle. In ACM Transactions on Mathematical Software, Volume 37(3), article 24, 2010. © ACM Press. [ ACM Link ]. A preprint version is available [ Postscript / PDF ]
Edge-Selection Heuristics for Computing Tutte Polynomials. David J. Pearce, Gary Haggard and Gordon Royle. In the Chicago Journal of Theoretical Computer Science, Volume 2010, article 6, 2010. [ CJTCS Link ]. This is an extended version of our CATS paper (see below). A preprint version is available [ Postscript / PDF ]
Computing Tutte Polynomials. Gary Haggard, David J. Pearce and Gordon Royle, Isaac Newton Institute for Mathematical Sciences, #NI09024-CSM, 2009. [ Postscript / PDF / INI Website ]
Edge-Selection Heuristics for Computing Tutte Polynomials. David J. Pearce, Gary Haggard and Gordon Royle. In Proceedings of the Computing: The Australasian Theory Symposium, pages 153--162, 2009. A technical report version is available [ Postscript / PDF / PPT / Conference Website]
Visualizing the computation tree of the Tutte Polynomial. Bennett Thompson, David J. Pearce, Craig Anslow and Gary Haggard. In Proceedings ACM symposium on Software visuallization (SoftViz), pages 211--212, 2008. [ ACM Link / Conference Website ]
Visualising the Tutte Polynomial Computation. Bennett Thompson, David J. Pearce and Gary Haggard. In Proceedings of the New Zealand Conference on Software Engineering (SIENZ), 2007. [ Postscript / PDF / Powerpoint / Conference Website ]
History
The code released was originally based on that by Prof. Gary Haggard from Bucknell. He had developed a version in C over several years which was very efficient. Gary was visiting me at Victoria University of Wellington in 2007, and we decided to reimplemented his code in C++. This proved beneficial, since the new version is more modular and extensible. New features added included a proper cache replacement system + heuristics, different edge-selection heuristics and the ability to break up an intermediate graph when it is no longer biconnected.
Since then, Prof Gordon Royle has provide lots of help with the design and development of the tool; he has also been using it to investigate flow polynomials, and recently discovered a counter-example to a 25-year old conjecture by Dominic Welsh.
More recently, in 2009, Gary + myself computed the Tutte polynomial of the Truncated Icosahedron, which represents something of a landmark for us. This took about one week to compute on a grid of 150 machines and, for those particularly interested in such things, the polynomial is here and some more information can be found here.
Download
Release | Date | Arch | Files | Notes |
0.9.16 | December 2011 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.16.tgz | |
0.9.15 | September 2011 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.15d.tgz | |
0.9.14 | February 2011 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.14c.tgz | |
0.9.13 | November 2009 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.13.tgz | |
0.9.12 | August 2009 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.12.tgz | |
0.9.11 | August 2008 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.11.tgz | |
0.9.10 | August 2008 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.10.tgz | |
0.9.9 | July 2008 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.9.tgz | |
0.9.8 | June 2008 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.8.tgz | |
0.9.7 | April 2008 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.7.tgz | |
0.9.6 | August 2007 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.6.tgz | |
0.9.5 | August 2007 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.5.tgz | |
0.9.4 | August 2007 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.4.tgz | |
0.9.3 | August 2007 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.3.tgz | |
0.9.2 | August 2007 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.2.tgz | |
0.9.1 | June 2007 | UNIX (inc. Linux) / Cygwin | tuttepoly-v0.9.1.tgz |
Documentation
To build it, first run "./configure" from the base directory. If this is successful, you can then run "make" or "gmake" from the base directory. The executable file is left in the "tutte/" directory at the moment. NOTE: we recommend setting the CFLAGS and CXXFLAGS appropriately (e.g. as "-O2") before running "configure".
You can see some of the command-line options by running "tutte --help". Generally speaking the only real option you need to play with is the cache size. You want to set this to roughly about 80% of your machines physical RAM. For example, if my machine has 1GB of memory then I'll run it like this:
% tutte -c800M input-file
You'll find some sample input files in the "examples/".
Links
- C Code for computing Tutte Polynomials
- Wikipedia Entry on Tutte Polynomials
- Wikipedia Entry on Chromatic Polynomials
- There are two book chapters here and here about Tutte Polynomials and their applications.
- The Nauty Page --- Nauty is a tool used in our code for determining graph isomorphism.
- Some nice pages here and here about Knot Theory.