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.


2 Answers 2


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

sage: len(list(digraphs(4)))

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())))

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 :


Which also happens to contain several references that may suit your taste :-)



Counting unlabeled acyclic digraphs -- R. W. Robinson


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.