# iterate over all directed acyclic graphs (DAGs) on n vertices

Is there a simple way to iterate over all DAGs on n vertices?

So far, I do this via posets and gray code like shown below, but is it an overkill?

UPDATE. The code is corrected, thanks to tmonteil.

from sage.combinat.gray_codes import product as gc_product
def Dags0(n):
for P in Posets(n):
H = P.hasse_diagram()
E = list( set(H.transitive_closure().edges(labels=False)) - set(H.edges(labels=False)) )

G = H.copy()
C = G.canonical_label()
CC = set(C.dig6_string())
yield C

for e,d in gc_product(*len(E)):
if d>0:
else:
G.delete_edge(E[e])
C = G.canonical_label()
dig6 = C.dig6_string()
if dig6 not in CC:
yield C

edit retag close merge delete

No, nauty does not seem to support generation of DAGs. It can filter graphs based on acyclicity, but this would be inefficient as it was discussed below.

Sort by » oldest newest most voted

First, it seems that your algorithm is not correct (it probably does not take into accounts new symmetries created when adding/removing edges). Indeed, if we count the graphs it produces, we get the following list:

sage: [len(list(Dags(i))) for i in range(7)]
[1, 1, 2, 6, 33, 361, 8044]


Which does not correspond to the OEIS sequence of unlabeled DAGs:

sage: s = oeis("A003087") ; s
A003087: Number of acyclic digraphs with n unlabeled nodes.
sage: s.first_terms()[:7]
(1, 1, 2, 6, 31, 302, 5984)


Here is a way to construct unlabeled DAGs. Since the fact of being a DAG is an hereditary property (it remains true when we remove some edges), we can use the digraphs function:

sage: def Dags(n):
....:     return digraphs(n, property=lambda G : G.is_directed_acyclic())


We can check that we got the correct statistics:

sage: [len(list(Dags(i))) for i in range(7)]
[1, 1, 2, 6, 31, 302, 5984]


It is unfortunately slower than your method, hence it might be interesting to fix it and improve Sage capabilities.

For more details about the digraphs function, see:

sage: digraphs?

more

Thank you for pointing out to the issue of over-counting. I've updated my code to correct this issue.

As for your suggestion to use digraphs with testing for acyclicity -- unfortunately, it is quite inefficient as compared to my algorithm. For example, at my system already for $n=6$ your approach is 5 times slower than mine. How inefficient is going over all directed graphs can be seen from comparing OEIS A003087 (number of DAGs) and OEIS A000273 (number of all DiGraphs).

The algorithm in the digraph function is not running over all directed graphs and then filtering the good ones. Instead, it cuts branches as soon as the property is not satisfied during the generation.

It is not efficient enough anyway. For example, for $n=7$ counting all DAGs with my approach takes less than 2 minutes, but it takes much much longer for digraphs (I was not patient enough to wait until it finishes).