Computational Combinatorics

Category: Tips and Tricks

Best Practices for Scientific Computing

The following tweet found its way into my Twitter newsfeed.

I thought it would be appropriate to take the advice found in this article and apply them specifically to computational combinatorics. In particular, they identify and outline eight best practices, which I will discuss individually. Further, during the discussion I will include how I apply (or will apply) these concepts during my own development process. Below, I have simply copied their “Summary of Best Practices”. You can investigate each item in more detail in the original article. I’ll add my own ideas under each main topic.

Caveat: I showed this paper to a software engineer (my wife) and she thought all of these items would be obvious to anyone with even a basic understanding of software engineering. However, as the original paper is written for biologists and this blog is written for mathematicians, I find it appropriate to cover these ideas.
Read the rest of this entry »

Finding and Counting Cliques with cliquer

For a graph G, a clique is a set S \subseteq V(G) such that all pairs of vertices in S are adjacent in G. Determining the maximum size of a clique in a graph is a classic NP-Complete problem, but sometimes you just need to find or count cliques anyway.

Today, we discuss the cliquer algorithm, as designed by Niskanen and Östergård. Their very efficient implementation is available on their cliquer homepage. The entire implementation is very succinct and can be used as a library. In fact, Sage uses cliquer for its backend for clique algorithms. The main algorithm computes the maximum (weighted) clique and also can count maximum or maximal (weighted) cliques. We focus on the unweighted case.
Read the rest of this entry »

Using TreeSearch for Parallel Computation

The previously described process of combinatorial search was extremely abstract on purpose. All of the computational experiments I design are implemented using TreeSearch. TreeSearch is my own software library for running combinatorial search in a parallel environment. It abstracts the notion of a search tree into a few basic operations, which are then implemented for each individual experiment. This allows the interface for managing thousands of parallel jobs to be common among all of the other projects in my SearchLib software collection.

This library is a C++ implementation of the recursive search, including the augmentation step, pruning, and outputting solutions. In addition, the library manages tracking statistics and distributing independent jobs to a supercomputer. Today, we’ll discuss how to use TreeSearch for your own computational experiment. If you don’t want to use my code, you can use it as an example for how to manage a large number of parallel jobs.
Read the rest of this entry »

Computing Orbits with nauty

Now that we can compute canonical labelings with nauty, we will now find out how to modify that code in order to compute orbits of any rankable object within a graph. We will focus on the orbits of certain vertex sets, although the technique generalizes to k-tuples of vertices, as well. Really, all you need is an object with a ranking and unranking function to make this technique work.
Read the rest of this entry »

Canonical Labelings with Nauty

Here, I’ll describe how to actually compute a canonical labeling using nauty. The objects we will consider are graphs, directed graphs, and (vertex or edge) colored versions of those objects. This will lead into the next post where we will use nauty to compute orbits in these objects.
Read the rest of this entry »

Example: Piping geng

I realized shortly after writing yesterday’s post about using gtools that I did not properly explain the piping procedure for geng. To remedy that deficiency, I will provide a concrete example of how I used this method in actual research.

In this example, we will exactly characterize the infinite class of p-extremal graphs for p \leq 10. We’ll start by talking about the mathematics, and at the very end we will go into the concrete piping example. Theoretically, you could skip straight to the code, but you’ll miss out on the fact that the computer is simultaneously discovering and proving a structure theorem for an infinite class of graphs!
Read the rest of this entry »

Tips and Tricks: Using gtools

If you want to get down and dirty with computational methods but don’t want to do a lot of programming, you can get started now using Brendan McKay‘s gtools software, part of the nauty library. It’s free software, but you’ll need to compile it yourself. This software allows you to generate graphs in several different ways, usually finding all graphs with certain properties up to isomorphism. The output is not human-readable, but you can use the output to create graphs in Sage or just count the number of graphs with that property. Everything I write below is available in the user manual, but read ahead for a slightly different treatment.

Read the rest of this entry »