Connected Regular Graphs on 12 vertices.

Question

I'm trying to get a list of regular graphs on 12 vertices in g6 format.
I've spent a few days trying to unscramble the data at the Regular Graphs Page, but I can't unscramble the shortcode format. Also, with my limited linux experience, I've had no luck getting genreg to run. Specifically, I need the 1544 4-regular and 7848 5-regular graphs on 12 vertices. The 10778 4-regular graphs would also be nice.

Answer 1

According to the GENREG manual, the shortcode files do three things:

1. Encode the graph as an adjacency list.
2. Compress the adjacency list, so that for each vertex $i$ only neighbors $j>i$ are listed.
3. For each graph in the file, begin by giving the number of entries of the compressed list that are identical to the compressed list of the previous graph, and then only give the entries that are different.

This encodes a sequence of graphs as a (longer) sequence of integers; the .scd file has one integer per byte.

Here is some Mathematica code that undoes all of these steps:

adjacencyListGraph[list_] := 
 Graph @ Flatten @ Table[i <-> j, {i, Length[list]}, {j, list[[i]]}]

splitAdjacencyList[shortlist_, n_, d_] := 
 TakeList[shortlist, Table[d - Count[shortlist, i], {i, n}]]

parseShortcode[byteList_, n_, d_] :=
 Module[{graphcode = Table[0, n*d/2], newcount, i = 1},
  Reap[While[i < Length[byteList],
     newcount = n*d/2 - byteList[[i]];
     graphcode[[-newcount ;;]] = byteList[[i + 1 ;; i + newcount]];
     i += (newcount + 1);
     Sow[adjacencyListGraph @ splitAdjacencyList[graphcode, n, d]]
     ]][[2, 1]]]

In reverse order, parseShortCode parses the bytes of an .scd file, where splitAdjacencyList figures out how to split up an adjacency list by vertex, and adjcencyListGraph turns the result into a graph. Note that parseShortCode needs to know $n$ (the number of vertices in a graph) and $d$ (the degree of each vertex) to parse the file.

For example, we can read the $3$-regular connected graphs on $10$ vertices:

example = Import["http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/SCD/10_3_3.scd", 
    "Byte"];
parsed = parseShortcode[example, 10, 3]

This gives a list of Mathematica graphs, which we can then export as a Graph6 string if we like. (Even for the $10778$ four-regular graphs on $13$ vertices, importing the graphs takes less than a second.)

Answer 2

I think Misha Lavrov's answer is excellent. Here I offer an alternative.

• nauty

It also seems to handle generating regular graphs quickly. For exmaples, there are 1547 4-regular 12-vertex graphs (including 1544 connected graphs and 3 disconnected graphs)

geng  12 -d4 -D4 -g

Only consider connected graphs.

geng  12 -d4 -D4 -g -c

Similar to Misha Lavrov, we can also import them with Mathematica, but the speed is mostly lost in the import process. But for the size of the data here, it's pretty fast.

 S = Import["!D:/nauty27r3/geng  12 -d4 -D4 ", "Graph6"]; // AbsoluteTiming

{0.966699, Null}