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
Included in the
nauty library are two data structures:
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.
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, we need a few bookkeeping items. The first is an options structure, which can be initialized with the line
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.)
To store a directed graph, simply use the
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.)
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.
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
ptn arrays are used for as input to
ptn array marks the positions of a partition of the vertices, and the vertices of each part are given by the order in
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 .
nauty pay attention to your partition, set
options.defaultptn = FALSE.
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.)
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.
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!
nauty User’s Guide.
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.