5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

Counting unlabeled acyclic digraphs -- R. W. Robinson

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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