Generators  Building levelk 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
level2 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 level3 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 level4 generators.
Among the 8501 level4 generators built with the rules from the 65 level3
generators, 1993 are non isomorphic.
After more than 10 hours of computation on a laptop, the program also
found the 91454 level5 generators.
The number
g_{k} of level
k generators, for
k > 0, is
1, 4, 65, 1993, 91454...
Download
Implementation notes
I used the program
Lev3Gen.java
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:

implement the rules to get levelk+1 generators
from levelk generators (see methods
buildGenerators in class Generator, ruleR1,
ruleR2, ruleR1multi and ruleR2multi in class Graph).

implement a simple (but exponential: 2^{nb of vertices of outdegree 2})
digraph isomorphism backtracking algorithm
(see method recIsomorphic in class Graph) which consists
in going through both graphs in the same time to try to identify their vertices.
If you know a better algorithm (still easy to implement) for digraphs
of maximum degree 3, please
contact me!