Best Practices for Scientific Computing

The following tweet found its way into my Twitter newsfeed.

Important paper: Best Practices for Scientific Computing http://t.co/GJc0fviciJ

— Mike Loukides (@mikeloukides) January 12, 2014

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.

Finding and Counting Cliques with cliquer

For a graph , a clique is a set such that all pairs of vertices in are adjacent in . 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.

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.

• Download the TreeSearch User Guide
• Download the TreeSearch Source Code

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.

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 -tuples of vertices, as well. Really, all you need is an object with a ranking and unranking function to make this technique work.

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.

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 -extremal graphs for . 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!

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.