<p>Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of <span class="math-container">$n$</span> 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 <span class="math-container">$n$</span> edges). The number of such digraphs is sequence <a href="https://oeis.org/A002861" rel="nofollow noreferrer">A002861</a> on the Online Encyclopedia of Integer Sequences.</p>
<p>We have discovered an enumeration algorithm with the following properties:</p>
<ul>
<li>every connected functional digraph (up to isomorphism) is generated;</li>
<li>no duplicates (with respect to graph isomorphism) are generated;</li>
<li>each functional digraph is generated in polynomial time (with respect to <span class="math-container">$n$</span>);</li>
<li>the algorithm uses polynomial auxiliary space, not counting the output (which is, of course, write-only).</li>
</ul>
<p>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 <em>all</em>, not necessarily connected functional digraphs (<a href="https://oeis.org/A001372" rel="nofollow noreferrer">A001372</a>)?</p>

CC BY-SA 4.0
2022-06-26T04:18:54.633Z
By the way, I’m wondering if this question would actually be better asked on MathOverflow. Any opinions on that?
Antonio E. Porreca
CC BY-SA 4.0
2022-06-26T07:57:43.673Z
Just following your OEIS link, in the 'formula' field, it gives an equivalence (to the CIK transform of directed trees). I haven't encountered the 'CIK' transform before, and the first description of it I can find is https://oeis.org/A032199  , but it does sound like a constructive enumeration of the objects in the sequence (if some details are filled in) and not just the construction of the number of objects. Can you comment on whether this meets the criteria of an algorithm you ask about?
JimN
CC BY-SA 4.0
2022-06-26T09:17:21.383Z
@JimN I am… really not sure. The description on [A032199](https://oeis.org/A032199), although it does indeed seem like it can generate the actual objects, appears to be a calculation “by hand”, and the [general description](https://oeis.org/transforms2.html) of the CIK transform seems to define it in terms of the CHK transform, based on the AIK transform, and the latter coincides with the INVERT transform, which works on the generating function of the sequence rather than on the $n$-th term. Knowing almost nothing about generating functions right now, I unfortunately don’t know how to comment.
Antonio E. Porreca
CC BY-SA 4.0
2022-06-26T17:45:59.107Z
Okay, let's instead try a constructive version of the 'Comment' field of A002861. Does your discovered enumeration algorithm go like this: generate all the functions that are on a tree-shape, then generate all the functions that are a 2-cycle with path-like branches coming out of the cycle, then generate all the functions that contain a 3-cycle with branches, and so on up until you get to one n-cycle?
JimN
CC BY-SA 4.0
2022-06-26T20:29:28.413Z
No, it’s very different from that. We start from the $n$-cycle, then merge adjacent trees (with an appropriate notion of merging) thus creating shorter cycles, and continue recursively until no further merging is possible. Then we go back up and try different merges in the previous steps. Several tricks are needed in order to avoid duplicates, but it all works out in the end.

Your proposed enumeration is clearly the obvious one, and the first one we thought about, but we weren’t able to do it without creating isomorphic graphs.
Antonio E. Porreca
CC BY-SA 4.0
2022-06-26T21:45:12.567Z
I see - thanks for the description. I don't see anything on the OEIS page that suggests that construction, and (getting back to your original question) I'm not aware of any explicitly-described algorithm to generate these...  Another thought: I believe Nauty's geng has a directed graph version or option, and probably takes some parameters for generating (di)graphs with maximum/minimum (in/out)degrees... of course, this does a kind of brute-force generation and filters out isomorphic duplicates, but it does generate things and maybe it would be worthwhile to time-test yours against that
JimN
CC BY-SA 4.0
2022-06-28T14:48:24.887Z
@JimN Thanks for the suggestion about Nauty, it seems like our algorithm is more efficient for large ($n \ge 19$) digraphs. If anyone’s interested, the Nauty approach is based on using the `geng` program to generate all suitable $n$-vertex undirected connected graphs with $n$ or $n-1$ edges, and then piping the output to `watercluster2` in order to generate the induced digraphs, while forcing an outdegree of 1. (I also reached out to the maintainer, and he thinks our approach might be novel.)
Antonio E. Porreca
CC BY-SA 4.0
2023-04-05T07:30:24.907Z
Not really an answer to my original question, but in the end we wrote a [paper](https://doi.org/10.48550/arXiv.2302.13832) on the subject, which is currently under review, as well as an [implementation](https://github.com/aeporreca/funkdigen2) which is much faster than the above-mentioned `nauty` tools.
Antonio E. Porreca
<cc.complexity-theory><ds.algorithms><graph-algorithms><graph-isomorphism><enumeration>
Efficient enumeration of connected functional digraphs (up to isomorphism)
Antonio E. Porreca
# Efficient enumeration of connected functional digraphs (up to isomorphism)

(Asked by: username_0 on 2022-06-24)

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](https://oeis.org/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](https://oeis.org/A001372))?

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, graph-isomorphism, enumeration

> **Comments:**
> **username_0**: By the way, I’m wondering if this question would actually be better asked on MathOverflow. Any opinions on that?  
> **username_1**: Just following your OEIS link, in the 'formula' field, it gives an equivalence (to the CIK transform of directed trees). I haven't encountered the 'CIK' transform before, and the first description of it I can find is https://oeis.org/A032199  , but it does sound like a constructive enumeration of the objects in the sequence (if some details are filled in) and not just the construction of the number of objects. Can you comment on whether this meets the criteria of an algorithm you ask about?  
> **username_0**: @username_1 I am… really not sure. The description on [A032199](https://oeis.org/A032199), although it does indeed seem like it can generate the actual objects, appears to be a calculation “by hand”, and the [general description](https://oeis.org/transforms2.html) of the CIK transform seems to define it in terms of the CHK transform, based on the AIK transform, and the latter coincides with the INVERT transform, which works on the generating function of the sequence rather than on the $n$-th term. Knowing almost nothing about generating functions right now, I unfortunately don’t know how to comment.  
> **username_1**: Okay, let's instead try a constructive version of the 'Comment' field of A002861. Does your discovered enumeration algorithm go like this: generate all the functions that are on a tree-shape, then generate all the functions that are a 2-cycle with path-like branches coming out of the cycle, then generate all the functions that contain a 3-cycle with branches, and so on up until you get to one n-cycle?  
> **username_0**: No, it’s very different from that. We start from the $n$-cycle, then merge adjacent trees (with an appropriate notion of merging) thus creating shorter cycles, and continue recursively until no further merging is possible. Then we go back up and try different merges in the previous steps. Several tricks are needed in order to avoid duplicates, but it all works out in the end.  Your proposed enumeration is clearly the obvious one, and the first one we thought about, but we weren’t able to do it without creating isomorphic graphs.  
> **username_1**: I see - thanks for the description. I don't see anything on the OEIS page that suggests that construction, and (getting back to your original question) I'm not aware of any explicitly-described algorithm to generate these...  Another thought: I believe Nauty's geng has a directed graph version or option, and probably takes some parameters for generating (di)graphs with maximum/minimum (in/out)degrees... of course, this does a kind of brute-force generation and filters out isomorphic duplicates, but it does generate things and maybe it would be worthwhile to time-test yours against that  
> **username_0**: @username_1 Thanks for the suggestion about Nauty, it seems like our algorithm is more efficient for large ($n \ge 19$) digraphs. If anyone’s interested, the Nauty approach is based on using the `geng` program to generate all suitable $n$-vertex undirected connected graphs with $n$ or $n-1$ edges, and then piping the output to `watercluster2` in order to generate the induced digraphs, while forcing an outdegree of 1. (I also reached out to the maintainer, and he thinks our approach might be novel.)  
> **username_0**: Not really an answer to my original question, but in the end we wrote a [paper](https://doi.org/10.48550/arXiv.2302.13832) on the subject, which is currently under review, as well as an [implementation](https://github.com/aeporreca/funkdigen2) which is much faster than the above-mentioned `nauty` tools.  

---

## 0 answers

