Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known as connected digraphs with uniform outdegree 1, or connected functions, or connected mapping patterns, or rings and branches with $n$ edges). The number of such digraphs is sequence A002861 on the Online Encyclopedia of Integer Sequences.
We have discovered an enumeration algorithm with the following properties:
- every connected functional digraph (up to isomorphism) is generated;
- no duplicates (with respect to graph isomorphism) are generated;
- each functional digraph is generated in polynomial time (with respect to $n$);
- the algorithm uses polynomial auxiliary space, not counting the output (which is, of course, write-only).
Until now, we were not able to find an algorithm with these four properties in the literature (actually, we haven’t found any nontrivial algorithm at all). Is there any known result about this problem or the related problem of enumerating all, not necessarily connected functional digraphs (A001372)?