Resources

This page contains a list of resources to help with computational combinatorics. Please email me if you would like to add something to this list.

Online Resources

ISGCI: Information System on Graph Classes and their Inclusions “ISGCI is an encyclopaedia of graphclasses with an accompanying java application that helps you to research what’s known about particular graph classes.” Useful for learning more about the types of graphs you are working with, including code examples.

House of Graphs is a collection of examples of some rare graph families, such as cages, strongly-regular graphs, and Ramsey graphs.

FXT: A library of algorithms by Jörg Arndt contains descriptions and code samples for many really fast algorithms. These algorithms are also featured in his book, Matters Computational [Amazon].

Sage

Sage is an open-source Maple/Mathematica replacement with some nice combinatorics features. Useful for very quick exploration of example objects, and even some robust computational experiments.

Sage Tutorial. This tutorial can get you started with the basics of Sage.

Python Tutorial. Since Sage is built within Python, you may need to use more advanced Python programming.

Graph Library. See also Nathann Cohen’s very short introduction to the graph library.

NetworkX is an alternate graph library. I use it only for the advanced drawing techniques. See a list of drawing examples.

Here are a few Sage worksheets that demonstrate some of the graph features of Sage:

Optimization Software

GLPK: the GNU Linear Programming Kit is open-source and easy to work with library. It also includes an exact solver.

COIN-OR: COmputational INfrastructure for Operations Research is a much larger open-source library. It includes many other types of optimization, including mixed integer programming.

CPLEX is a commercial solver, currently owned by IBM. Academic Licenses are available, and worth the hassle as CPLEX is very fast. One of the best integer program solvers available.

Gurobi is another commercial solver, built by the original programmers of CPLEX. Also available with an academic license and very fast.

C/C++ Software

nauty is Brendan McKay‘s graph generation and isomorphism-testing library. Includes geng, the fastest implementation of isomorph-free generation available.

plantr/fullgen generates planar graphs very very quickly.

buckgen generates fullerenes (also known as “buckyballs”).

surftri generates triangulations of surfaces.

snarkhunger generates snarks.

triangleramsey finds Ramsey numbers R(K_3,G) for a given graph G.

cliquer is a very fast clique-finding algorithm, by Patric Östergård.

SearchLib is my collection of computational experiments. Most projects are specific to certain research projects, but the Utilities and TreeSearch projects include helpful tools for computational combinatorics software. Specifically, TreeSearch is an abstraction of a backtracking search to run on distributed environments. All other SearchLib projects are built using TreeSearch.