Generators - Building level-k generators
generators were introduced by
and his coauthors in their RECOMB 2008 paper
to describe the structure of
networks. A case analysis to build all
level-2 generators is presented
in the detailed version
of this article
, and later generalized as a
algorithm by Steven Kelk followed
by a digraph isomorphism test
to build all 65 level-3 generators.
shows in Section 3 how general level-k
can be decomposed into generators of level at most k
It also provides rules to build level-k
+1 generators recursively
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
generators, for k
> 0, is
1, 4, 65, 1993, 91454...
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
implement the rules to get level-k+1 generators
from levelk generators (see methods
buildGenerators in class Generator, ruleR1,
ruleR2, ruleR1multi and ruleR2multi in class Graph).
implement a simple (but exponential: 2nb 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