### Canonical Labelings with Nauty

#### by Derrick Stolee

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.

*Most of what I discuss here is more thoroughly described in the nauty User’s Guide. However, some of the constructions are found in hidden corners of the guide. This is simply an attempt to present another perspective on the ways to interact with nauty.*

### Graphs

Included in the `nauty`

library are two data structures: `graph`

and `sparsegraph`

. The `graph`

structure is a bit-packed adjacency matrix while the `sparsegraph`

structure is a single-dimensional-array version of an adjacency list. I prefer using the `sparsegraph`

because it is easier to work with and I do not find a large performance loss using this structure. (One of my personal goals is to have readable code, and `sparsegraph`

makes that goal easier, too.) Every call to `nauty`

has a `graph`

pointer in the function definition, but passing a `sparsegraph`

pointer will also work.

A `sparsegraph`

has three main arrays: , , and . The array stores the actual links for the adjacency list, stores the index within to begin the adjacencies corresponding to the vertex , and stores the degree of the vertex (and hence the number of consecutive positions within that correspond to the vertex ). Variables and store the number of vertices and number of directed edges (so, twice the number of undirected edges), respectively.

The array does not have to be compressed. In fact, since we are typically augmenting a graph to add vertices and edges, I let be the maximum order of a generated graph and store and have the array have positions.

#### The call to `nauty`

To call `nauty`

, we need a few bookkeeping items. The first is an options structure, which can be initialized with the line

`static DEFAULTOPTIONS_SPARSEGRAPH(options);`

when using `sparsegraph`

. Then, the `options`

can give several important options to the `nauty`

function. Most importantly, this controls whether the graph is directed and whether we want a canonically-labeled graph in the result.

Also, we’ll need what is called a *workspace*. This is a set of memory that the `nauty`

function will use for all of its data. It will not allocate heap memory other than this workspace. See the code to see how this is set up.

It is best to see the actual code to see how everything is set up, so I have created a source code file nautyexamples.c. This file contains the canonical labeling methods descibed here, as well as the constructions described below. See the comments at the top of the page for compilation instructions and the comments above the `main()`

method to see how to send arguments and input to the program. (You can disable the `main()`

method and use it as a library if you want.)

### Directed Graphs

To store a directed graph, simply use the `graph`

or `sparsegraph`

strucutres without bidirectional edges, the same way an adjacency matrix or adjacency list loses symmetry. Keep in mind, now, that is actually equal to the number of edges. (In general, these structures consider an undirected graph simply as a directed graph with the property that the edge exists if and only if the edge exists.)

To run `nauty`

with a directed graph, simply change the option `opt.directed`

to TRUE. This tells the `nauty`

algorithm to be aware of direction when building the canonical labeling. This is the only change required, including in the following two colored versions of the canonical labeling.

### Vertex-Colored Graphs

Consider pairs where is a graph and is a (possibly improper) -coloring of . Over these pairs, we can define a *color-preserving isomorphism* from to as a bijection such that is an isomorphism from to and for all . We will wish to compute canonical labelings for these isomorphism classes.

This type of coloring is exactly what the `lab`

and `ptn`

arrays are used for as *input* to `nauty`

. The `ptn`

array marks the positions of a partition of the vertices, and the vertices of each part are given by the order in `lab`

.

To reflect a coloring , iteratively place the vertices in to the beginning of `lab`

, for all in increasing order. Let and let `ptn`

have positive value everywhere except value 0 at the positions for each . The 0’s dictate the *end* of a part. The ordering of doesn’t matter, only that appears before .

To have `nauty`

pay attention to your partition, set `options.defaultptn = FALSE`

.

Now, running `nauty`

with these changes will return a canonical labeling under the conditions that vertices with color are within the positions occupied by . Therefore, the order of your colors is important for the canonical labeling.

#### Permuting the Colors

Sometimes we think of “non-isomorphic colorings” as having no order to the color set and hence the colors can be permuted. This type of “isomorphic coloring” can be tested by adding a new vertex for each color adjacent to its color class. Then, use the current method to 2-color the graph as “regular vertices” and as “color vertices” to avoid these two types of vertices from interacting. (See “Exchangeable vertex colours” in Section 12 of the Users’ Guide for more.)

### Edge-Colored Graphs

Suppose we instead have pairs where is a graph and is an *edge-coloring* and wish to canonically label these pairs under the same kind of isomorphism as vertex-colored graphs. We cannot simply partition the edges of the graph, so we instead build a *layered* graph.

#### The -Layered Graph

If we use colors, the simplest thing to do is to replace each vertex with some fixed connected graph of vertices . (A path is easy, but a cycle is even simpler to implement.) Then, if an edge has color , we add an edge between and . Finally, we partition these vertices by the superscripts: . Now, any permutation of carries over to a permutation to all by the path that replaced each vertex. By looking only at the order on , we have a canonical label of .

#### The Binary Layered Graph

The -layered graph has one big issue: when is large, we are making many layers and this is wasteful. Instead, let and use layers. We will associate the color with the -bit binary representation of the number and for every edge colored we will place an edge between the copies of and in *all layers with a 1* in . Now, we have only a logarithmic number of layers, but still a layer-preserving isomorphism between two binary layered graphs must have an edge appear in exactly the right arrangement of layers, so color is preserved.

#### Trigraphs

Most of the previous constructions were given in a very hypothetical sense, so let’s see a very important application of these ideas.

Suppose we are generating graphs by starting with vertices and adding edges *and* non-edges. What I mean is this: every pair of vertices starts as “undecided” and we will augment the structure by setting some pairs to “edges” and some pairs to “non-edges”. Essentially, we are starting with an uncolored copy of and coloring the edges with 1 (edge) and 0 (non-edge).

A *trigraph* is a 3-edge-colored copy of where all pairs have color black (edge), white (non-edge), or gray (undecided). As combinatorial objects, these have been thought of as partial realizations of actual graphs and the “full” realizations change the gray edges to black or white to create a traditional graph. For this view, see Chudnovsky (2006) or Martin and Smith (2012) for some applications.

In the graph generation case, Hartke and I (2012+) used this to generate uniquely -saturated graphs. In the implementation, we used a 2-layered graph to store the trigraphs thinking of the gray edges as non-edges and black and white edges as a 2-coloring of a certain graph. Letting the gray edges be non-edges in the layered graph is possible only because every pair has one of three colors. Specifically, the gray edges start as the majority of edges, so to keep the structure spare in early steps we leave out the gray edges.

#### Permuting the Colors

Again, if we with to allow the colors to be permuted when testing isomorphism of two edge-colorings, we must use a different construction. First, for colors we must use the -layer construction, where every layer corresponds to a color. Also, all copies of a vertex must be pairwise adjacent to allow for any permutation of the layers. Finally, instead of partitioning the layers, make every vertex in layer adjacent to some new vertex and place into a second partition (separating “normal vertices” from “color vertices”).

### Exercise: Totally-Colored Graphs

A *total coloring* is a coloring of both the vertices and edges. Try to think of a construction that allows a canonical labeling of a totally-colored graph. What happens when we wish to permute the colors? Be careful: if the color changes, it should change to the same color for both the vertices *and* edges!

### References

#### nauty

B. McKay, `nauty`

User’s Guide.

#### Trigraphs

M. Chudnovsky. Berge trigraphs. *J. Graph Theory*, 53(1), pages 1-55, (2006).

R. Martin, J. Smith, Induced saturation number, *Discrete Mathematics*, 312(21), pages 3096-3106 (2012).

S. Hartke, D. Stolee, Uniquely -Saturated Graphs, preprint.

Thanks, great post. Can you publish the answer to the exercises as well (especially a construction of totally-colored graph)?