Generators - Building level-k generators

Two of the 1993 level-4 generators
Level-k generators were introduced by van Iersel and his coauthors in their RECOMB 2008 paper to describe the structure of simple level-k networks. A case analysis to build all level-2 generators is presented in the detailed version of this article, and later generalized as a brute force algorithm by Steven Kelk followed by a digraph isomorphism test to build all 65 level-3 generators.

This submitted article shows in Section 3 how general level-k networks can be decomposed into generators of level at most k. It also provides rules to build level-k+1 generators recursively from level-k generators.

The program below implements the rules and can be used directly to build all level-4 generators. Among the 8501 level-4 generators built with the rules from the 65 level-3 generators, 1993 are non isomorphic. After more than 10 hours of computation on a laptop, the program also found the 91454 level-5 generators.

The number gk of level-k generators, for k > 0, is 1, 4, 65, 1993, 91454...


Implementation notes

I used the program by Steven Kelk as a starting point. I separated the classes into different text files, and modified the main class, Generator, as well as the Graph class to: