Generators - Building level-k 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 g_k of level-k generators, for k > 0, is 1, 4, 65, 1993, 91454...

Download

• Program Generator (Java source)
• List of all level-k generators for k < 5 in the DOT language.
• Compressed list of all level-k generators for k < 6 in the DOT language.
• Philippe Gambette, Vincent Berry and Christophe Paul, The Structure of Level-k Phylogenetic Networks, 20^th Annual Symposium on Combinatorial Pattern Matching (CPM'09), 2009.

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 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: 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!