Generating all non-isomorphic connected graphs of size N using NAUTY

Background§

Graphs§

A graph is a collection of two sets: a set of vertices $(V)$ and a set of edges $(E)$ connecting those vertices.

$$ \begin{aligned} V &= \lbrace v_1, \cdots, v_n \rbrace \\ E &= \lbrace e_1, \cdots, e_m \rbrace \\ \end{aligned} $$

If we consider a graph of size $N$, we say that the graph has $N$ total vertices. Which allows for the possibility of $[N \times N]$ total edges (in the fully connected case).

Power Sets§

However, there is a combinatorially large number of graphs of size $N$ where the total number of edges $M$ is less than the fully connected case ($M \lt N$).

In the undirected case we can calculate the number of graphs using the powerset equation - as for every pair of vertices there can either be an edge or not:

$$ \mathcal{G} = 2^{n(n-1)/2} $$

For a graph of size $N=4$, the set of all graphs is of size 64.

Connectivity and Isomorphism§

Connectivity§

However, many of those graphs will include multiple components - meaning that the graph is disconnected.

Take for example the graph: $$ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix} $$ Which creates the following graph:

0 <-> 1
2 <-> 3

In this case, there is no path from 0 -> 2, or 0 -> 3, meaning the graph is disjoint.

Isomorphism§

Further, many of those graphs will be isomorphic - meaning that the topology of those graphs are identical.

Take for example the following pair:

$$ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ \end{pmatrix} $$ $$ \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1\\ 0 & 1 & 0 \\ \end{pmatrix} $$

which generates the graphs:

2 <-> 0 <-> 1
     and
0 <-> 1 <-> 2

In both cases, the labels on each of the vertices has changed, but the topology of the graph is identical. In cases where we are interested in studying topology of graphs, this topology would be double counted.

Problem Statement§

What we would like to do is identify all connected graphs of size $N$ that are non-isomorphic.

This would give us graphs without multiple connected components and with unique topologies within the set.

Generating Graphs with NAUTY§

NAUTY (which stands for no automorpshisms, yes?) is an incredibly fast C library that performs practical graph isomorphisms. It has a great commandline interface that can be used to generate graphs of exactly the constraints we mentioned above.

Installing§

You can install the tools from the original source an unofficial repo, or if you're using archlinux you can also install them from the AUR.

# installing the nauty toolkit
paru -S nauty

Generating Graphs§

Undirected Graphs§

The bread and butter tool for random graph generation within nauty is the geng command (generate graphs). Lets first create all connected non-isormorphic graphs of size 4 with geng.

# generates all connected graphs of size 4
geng -c 4

Which gives us the following response:

>A geng -cd1D3 n=4 e=3-6
CF
CU
CV
C]
C^
C~
>Z 6 graphs generated in 0.00 sec

These graphs are formatted using the graph6 file format, which is an efficient compression method of representing adjacency matrices as characters.

We can pipe these into another tool delivered with NAUTY called showg, which can represent those strings as adjacency matrices or other formats as well:

geng -c 4 | showg -a

Which gives us:

>A geng -cd1D3 n=4 e=3-6
>Z 6 graphs generated in 0.00 sec

Graph 1, order 4.
0001
0001
0001
1110

Graph 2, order 4.
0011
0001
1000
1100

Graph 3, order 4.
0011
0001
1001
1110

Graph 4, order 4.
0011
0011
1100
1100

Graph 5, order 4.
0011
0011
1101
1110

Graph 6, order 4.
0111
1011
1101
1110

I have also written my own tool for more conversions, convg, which can be used to generate flat adjacency matrices, DOT formats, and more:

geng -c 4 | convg -F flat

0001000100011110
0011000110001100
0011000110011110
0011001111001100
0011001111011110
0111101111011110

Directed Graphs§

geng will only generate undirected graphs, but we can use another tool within the suite to create all directed versions of a set of graphs.

This tool, watercluster2, is a faster improvement over the original tool, directg, and we'll be using it for this example.

In this example we'll be generating all connected non-isomorphic directed graphs of size 3.

geng -c 3 | watercluster2 Z

>A geng -cd1D2 n=3 e=2-3
>Z 2 graphs generated in 0.00 sec
&B?o
&B@o
&BHo
&B@_
&BH_
&BH?
&BP_
&BCo
&BSo
&BWo
&BKo
&B[o
&B\o
Number of directed graphs: 13

We can then visualize these in their DOT file format with convg

geng -c 3 | watercluster2 Z | convg -F dot

digraph graph_1 {
2 -> 0;
2 -> 1;
}
digraph graph_2 {
1 -> 2;
2 -> 0;
2 -> 1;
}
digraph graph_3 {
0 -> 2;
1 -> 2;
2 -> 0;
2 -> 1;
}
digraph graph_4 {
1 -> 2;
2 -> 0;
}
digraph graph_5 {
0 -> 2;
1 -> 2;
2 -> 0;
}
digraph graph_6 {
0 -> 2;
1 -> 2;
}
digraph graph_7 {
0 -> 1;
1 -> 2;
2 -> 0;
}
digraph graph_8 {
1 -> 0;
2 -> 0;
2 -> 1;
}
digraph graph_9 {
0 -> 1;
1 -> 0;
2 -> 0;
2 -> 1;
}
digraph graph_10 {
0 -> 1;
0 -> 2;
2 -> 0;
2 -> 1;
}
digraph graph_11 {
0 -> 2;
1 -> 0;
2 -> 0;
2 -> 1;
}
digraph graph_12 {
0 -> 1;
0 -> 2;
1 -> 0;
2 -> 0;
2 -> 1;
}
digraph graph_13 {
0 -> 1;
0 -> 2;
1 -> 0;
1 -> 2;
2 -> 0;
2 -> 1;
}

Conclusion§

And that's all there is to it!

We are able to generate all connected non-isomorphic graphs of size $N$ using the nauty suite of tools and then visualize them or further process them with convg.

References§

1. McKay, B.D. and Piperno, A., Practical Graph Isomorphism, II, Journal of Symbolic Computation, 60 (2014), pp. 94-112, https://doi.org/10.1016/j.jsc.2013.09.003
2. Nauty and Traces User Guide, http://users.cecs.anu.edu.au/~bdm/nauty/nug28.pdf
3. Graph6 File Format, http://users.cecs.anu.edu.au/~bdm/data/formats.txt