<p>If you are looking for an implementation, Sage knows how to generate general digraphs up to isomorphism</p>

<pre><code>sage: len(list(digraphs(4)))
218
</code></pre>

<p>You can then plug in a "test" method if you just want the acyclic ones :</p>

<pre><code>sage: len(list(digraphs(4, property = lambda g:g.is_directed_acyclic())))
31
</code></pre>

<p>It returns 302 digraphs on 5 vertices, and 5984 on 6 vertices. But I am a bit scared to try larger values :-)</p>

<p>By the way, giving those values to the OEIS returns the expected sequence :</p>

<p><a href="http://oeis.org/search?q=1,2,6,31,302,5984&amp;language=english&amp;go=Search">http://oeis.org/search?q=1,2,6,31,302,5984&amp;language=english&amp;go=Search</a></p>

<p>Which also happens to contain several references that may suit your taste :-)</p>

<p>Nathann</p>

CC BY-SA 2.5
2011-02-26T21:36:31.843Z
2011-02-26T21:36:31.843Z
Nathann Cohen
<p><a href="http://www.springerlink.com/content/1716582847315l87/" rel="nofollow">Counting unlabeled acyclic digraphs -- R. W. Robinson</a></p>

CC BY-SA 2.5
2011-02-26T22:28:02.973Z
2011-02-26T22:28:02.973Z
Pratik Deoghare
<p>I'm looking for an algorithm to efficiently generate all unlabeled acyclic digraphs of a given order.  (By "unlabeled" I mean that no two of the generated digraphs should be isomorphic.)
Thanks</p>

<p>Edit: removed the word "enumeration" from title; I made the original title "Enumeration/generation of unlabeled acyclic digraphs" in a misguided effort to increase the number of possible answers; I had conjectured, incorrectly, that enumeration algorithms could be easily adapted to generate all the enumerated digraphs; now I realize this conjecture is wrong, hence the edited title emphasizes that I'm interested in an algorithm for generating (and not just enumerating) unlabeled acyclic digraphs.</p>

<ds.algorithms><graph-algorithms><directed-acyclic-graph>
Generation of unlabeled acyclic digraphs
kjo
# Generation of unlabeled acyclic digraphs

(Asked by: username_0 on 2011-02-26)

I'm looking for an algorithm to efficiently generate all unlabeled acyclic digraphs of a given order. (By "unlabeled" I mean that no two of the generated digraphs should be isomorphic.)
Thanks

Edit: removed the word "enumeration" from title; I made the original title "Enumeration/generation of unlabeled acyclic digraphs" in a misguided effort to increase the number of possible answers; I had conjectured, incorrectly, that enumeration algorithms could be easily adapted to generate all the enumerated digraphs; now I realize this conjecture is wrong, hence the edited title emphasizes that I'm interested in an algorithm for generating (and not just enumerating) unlabeled acyclic digraphs.

**Tags:** ds.algorithms, graph-algorithms, directed-acyclic-graph


---

## 2 answers

### Answer by username_1 on 2011-02-26. Score: 5 | Accepted answer

If you are looking for an implementation, Sage knows how to generate general digraphs up to isomorphism
sage: len(list(digraphs(4)))
218

You can then plug in a "test" method if you just want the acyclic ones :
sage: len(list(digraphs(4, property = lambda g:g.is_directed_acyclic())))
31

It returns 302 digraphs on 5 vertices, and 5984 on 6 vertices. But I am a bit scared to try larger values :-)
By the way, giving those values to the OEIS returns the expected sequence :
http://oeis.org/search?q=1,2,6,31,302,5984&language=english&go=Search
Which also happens to contain several references that may suit your taste :-)
Nathann


---

### Answer by username_2 on 2011-02-26. Score: 3

[Counting unlabeled acyclic digraphs -- R. W. Robinson](http://www.springerlink.com/content/1716582847315l87/)


---

