Computational Combinatorics

Month: September, 2012

Things a Graph Theorist Should Do at Least Once

The theory blogs have been repeating the idea of “Things a [insert field] researcher should do at least once” including theoretical computer science, complexity theory, and algorithmic game theory. I figured I should chime in with what a graph theorist should do at least once.
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 »

Is anybody out there?

Being 8 weeks and 8 posts into this blog, I thought I’d do a quick status check. Is anybody reading?
Read the rest of this entry »

Ranking and Unranking of Combinations and Permutations

Now that we’ve discussed a nice standard example of canonical deletion, I want to get into more complicated uses. These techniques use more complicated augmentations and deletions, and hence require a little more delicate description of orbit calculations. In order to get to those, we need to be able to store and manipulate subsets of things. Another way to think of “subsets of things” is combinations, especially when we know the size of the subset.

Given a set X, we will discuss the power set 2^X of all subsets of X, the k-subsets \binom{X}{k}, the k-tuples X^k, and the k-permutations (X)_k. There are multiple ways to store a given subset, tuple, or permutation, but what is more important is how to store a list of information over the entire collection of these objects. My favorite method is to use a ranking function, which assigns each object an integer which I can use as an array position. Then, an unranking function will invert this process.

This area has a long history, with several different methods of ranking and unranking the objects competing for dominance in several measures of quality. My favorite measure is “readability” and/or “ease of programming” but definitely “computation speed” is important, too. However, sometimes ranking is fast and unranking is slow, sometimes the ranking and unranking is fixed to a certain order, such as lexicographic order.

Today we’ll talk about several ranking and unranking procedures, and the next post will discuss how to use these ranking/unranking functions to compute orbits of these objects for a graph with symmetry.
Read the rest of this entry »