Computing Orbits with nauty

by Derrick Stolee

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.

While nauty computes a canonical labeling, it is also computing the automorphism group of a graph. It provides this automorphism group as a set of generators as it discovers them. The way it provides these generators is via a function pointer in the options structure: options.userautomproc. Set this to an appropriately-typed function, and you can store or compute with every generator it finds.

Our method to compute orbits is to take these generators and use them to combine disjoint sets of objects. However, if our objects are vertices, then nauty calculates the orbits for us.

Orbits of Vertices

If you noticed from the code in nautyexamples.c (from the nauty intro post), in addition to the lab and ptn arrays, there is a third array, orbits that is passed to nauty. This orbits array is write-only (it doesn’t matter what it contains before the call) and at the end orbits[i] stores the smallest index of a representative vertex in the vertex orbit containing the $i$ th vertex. So, if you want to consider only one vertex per orbit, only consider the vertices $i$ such that orbits[i] == i.

In order to consider more complicated objects, we’ll need to compute the orbits ourselves.

Disjoint-Set Forests

First, let us briefly discuss an important data structure, the disjoint-set forest. This structure has two main functions: storing disjoint sets and combining two disjoint sets into one. Essentially, every set is a rooted tree, except the children point to thei parent. So, every element is given a parent, unless it is the root, where instead we place the negative of the depth of that tree, (or its rank). A slightly less standard, but helpful in our case, way to signal a root is to instead store the negative of the size of the set. This allows us to properly store arrays of our orbits.

Since our objects will be rankable, we can associate every object with a non-negative number. This allows us to store the disjoint-set forest as an integer array a with enough positions that the rank of every object is a position of the array. Then, a[i] will store either the parent of the object with rank $i$ or the depth of the tree, negated. When the array is initialized, every element will contain $-1$ .

To check if two elements are in the same set, trace the parent pointers until reaching a negative number and report that index. If the index is the same, they are in the same set. The getRoot(i) method peforms this function.

To join two sets, find the roots and we will assign one to be the parent of the other. To keep the getRoot(i) method running quickly, we will select the set of smaller set to be placed under the root of larger set. If they have equal size, we can assign any one to the other. We then modify the root to have the sum of the sizes. This is how the union(x,y) method combines the sets containing $x$ and $y$ .

Using Automorphisms

Two objects $X, Y$ are in the same orbit if there is an automorphism $\sigma \in \mathrm{Aut}(G)$ such that $\sigma(X) = Y$ (equivalently, $X = \sigma^{-1}(Y)$ ). However, $\sigma$ may be a complicated combination of generators.

Since nauty provides generators as it finds them, we will perform all the orbit calculations for a given generator and then forget about it. (The word for this is “on-line” computation.) Let $\sigma_1,\dots, \sigma_g$ be the generators we receive from nauty, in order. Let $\Gamma_i = \langle \sigma_1, \dots, \sigma_i\rangle$ be the group generated by the first $i$ generators. By convention, $\Gamma_0$ contains only the identity map.

Begin with every object in its own class (a[i] = -1 for all ranks). When the $i$ th generator, $\sigma_i$ , is reported, we will join two classes whenever $\sigma_i$ sends an object in one class to the other. Specifically, we only need to consider where $\sigma_i$ sends the parent of each class, since there is an invertible $\Gamma_{i-1}$ -action from any object to its parent. However, we must consider how multiple iterations of $\sigma_i$ send this parent, as the generator may have large order. For each parent of a class, we can stop iterating when our function sends us back to that object.

Example Code

The example code is given in a few files this time:

translation.c and translation.h store a few ranking/unranking methods (and helper methods).
orbitexamples.c contains the code for the orbit calculation and an executable which reads graphs and computes the $k$ -set orbits.

Look inside orbitexamples.c for compilation instructions. If you run the resulting executable, orbitexamples, with the arguments -k 1, we will compute the vertex orbits, -k 2 will give pair orbits, etc. The input file in.txt contains a description of the Petersen graph with these labels:

Running orbitexamples with different options will reveal the following output:

-k 1 will have output

Orbit 0:
{ 0 } { 1 } { 2 } { 3 }
{ 4 } { 5 } { 6 } { 7 }
{ 8 } { 9 }
-k 2 will have output

Orbit 0:
{ 0 2 } { 0 3 } { 1 3 } { 1 4 }
{ 2 4 } { 1 5 } { 2 5 } { 3 5 }
{ 4 5 } { 0 6 } { 2 6 } { 3 6 }
{ 4 6 } { 5 6 } { 0 7 } { 1 7 }
{ 3 7 } { 4 7 } { 6 7 } { 0 8 }
{ 1 8 } { 2 8 } { 4 8 } { 7 8 }
{ 0 9 } { 1 9 } { 2 9 } { 3 9 }
{ 5 9 } { 8 9 }
Orbit 1:
{ 0 1 } { 1 2 } { 2 3 } { 0 4 }
{ 3 4 } { 0 5 } { 1 6 } { 2 7 }
{ 5 7 } { 3 8 } { 5 8 } { 6 8 }
{ 4 9 } { 6 9 } { 7 9 }
-k 3 will have output

Orbit 0:
{ 1 4 5 } { 0 2 6 } { 3 5 6 } { 1 3 7 }
{ 4 6 7 } { 2 4 8 } { 0 7 8 } { 0 3 9 }
{ 2 5 9 } { 1 8 9 }
Orbit 1:
{ 0 1 2 } { 1 2 3 } { 0 1 4 } { 0 3 4 }
{ 2 3 4 } { 0 1 5 } { 0 4 5 } { 0 1 6 }
{ 1 2 6 } { 1 2 7 } { 2 3 7 } { 0 5 7 }
{ 2 5 7 } { 2 3 8 } { 3 4 8 } { 0 5 8 }
{ 3 5 8 } { 1 6 8 } { 3 6 8 } { 5 6 8 }
{ 5 7 8 } { 0 4 9 } { 3 4 9 } { 1 6 9 }
{ 4 6 9 } { 2 7 9 } { 4 7 9 } { 5 7 9 }
{ 6 7 9 } { 6 8 9 }
Orbit 2:
{ 1 3 5 } { 2 4 5 } { 0 3 6 } { 2 4 6 }
{ 2 5 6 } { 4 5 6 } { 0 3 7 } { 1 4 7 }
{ 0 6 7 } { 3 6 7 } { 0 2 8 } { 1 4 8 }
{ 1 7 8 } { 4 7 8 } { 0 2 9 } { 1 3 9 }
{ 1 5 9 } { 3 5 9 } { 0 8 9 } { 2 8 9 }
Orbit 3:
{ 0 1 3 } { 0 2 3 } { 0 2 4 } { 1 2 4 }
{ 1 3 4 } { 0 2 5 } { 1 2 5 } { 0 3 5 }
{ 2 3 5 } { 3 4 5 } { 1 3 6 } { 2 3 6 }
{ 0 4 6 } { 1 4 6 } { 3 4 6 } { 0 5 6 }
{ 1 5 6 } { 0 1 7 } { 0 2 7 } { 0 4 7 }
{ 2 4 7 } { 3 4 7 } { 1 5 7 } { 3 5 7 }
{ 4 5 7 } { 1 6 7 } { 2 6 7 } { 5 6 7 }
{ 0 1 8 } { 1 2 8 } { 0 3 8 } { 1 3 8 }
{ 0 4 8 } { 1 5 8 } { 2 5 8 } { 4 5 8 }
{ 0 6 8 } { 2 6 8 } { 4 6 8 } { 2 7 8 }
{ 3 7 8 } { 6 7 8 } { 0 1 9 } { 1 2 9 }
{ 2 3 9 } { 1 4 9 } { 2 4 9 } { 0 5 9 }
{ 4 5 9 } { 0 6 9 } { 2 6 9 } { 3 6 9 }
{ 5 6 9 } { 0 7 9 } { 1 7 9 } { 3 7 9 }
{ 3 8 9 } { 4 8 9 } { 5 8 9 } { 7 8 9 }

This should confirm what we already know about the Petersen graph: it is vertex-transitive, it is edge-transitive (and non-edge transitive), and there are four types of 3-sets: independent vertices, paths of length 2, an edge with a vertex that are in a 5-cycle, and an edge with a vertex that are not in a 5-cycle.

Working with Other Objects or Graphs

To adapt the code to work with other objects, simply replace the ranking/unranking functions between sets and integers within the generator function. To adapt the code to work with colored objects, simply be sure that the first $n$ vertices of the colored object correspond to the actual vertices of the graph. This will allow the automorphisms to work exactly the same way.

In a couple posts, we’ll see how to use the computation of these set-orbits in an actual experiment. For that use, we’ll use trigraphs (2-edge-colored graphs with possible non-edges) and also stabilize a pair of vertices (essentially 2-coloring the vertices of a graph in a very specific way).

The plan of the next two posts:

Orbital Branching
Uniquely $K_r$ -Saturated Graphs

Computational Combinatorics