Efficiently generating all regular/bidegreed graphs

Question

There is a related question on how to generate all regular graphs; however, the procedure is random and repeats the generated graphs. Plus, there is no stop condition, unless recording the total number of non-isomorphic graphs and matching it to the known numbers.

I wonder if there is a more efficient procedure that loops over all possible regular/bidegreed graphs? By more efficient, I mean return each regular graph only once, but if it's hard maybe other generation schemes that minimize the number of repetitions.

Ideally, I would like to have this procedure to generate all bidegreed graphs of order 20-30. But if bidegreed graphs are tough, at least for regular graphs.

By bidegreed graphs, I mean connected graphs that have only two possible values of degrees, $a$ and $a+1$, for any $a \ge 2$. The motivation for this is the reconstruction conjecture for this type of graphs.

Answer 1

For regular graphs, one of the standard tools would be geng, a C program from the Nauty package. Source code is included so you can inspect the algorithm. It is pretty efficient, for example all 5-regulars on 12 vertices (7849 graphs) are listed in one second on a desktop PC. For the special case of 4-regulars there is genquarticg which is even faster.

You probably know that the number of regular graphs grows pretty quickly as n grows, so if you want to explicitly generate all 5-regulars on 20 vertices ($4.22 \times 10^{15}$ graphs by OEIS A165626), you are in for some serious computation no matter how efficient your method is. If you don't actually need to explicitly generate each graph, but do some related task (e.g. just count the graphs), you may find faster ways.

(Edited) For bidegreed graphs as per your definition, where the two degrees differ by one, geng will still work since you can specify minimum and maximum degree, e.g. generate graphs whose vertices have degrees in the interval $[4,5]$. For more general bidegreed graphs, where the two degrees are further apart (say, 3 and 6), I don't know of an existing tool but I guess similar algorithms will work, and you might be able to tweak the geng program for this.

Answer 2

Kim et al. in this paper proposed a construction method (not based on swaps) to build all simple graphs realizing a given degree sequence. It should work with regular or bidegreed graphs too.

I don't know if any implementation of this algorithm is available, but if you find or do such an implementation, I would be interested to know about its practical efficiency.