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([2]*len(E)):
if d>0:
G.add_edge(E[e])
else:
G.delete_edge(E[e])
C = G.canonical_label()
dig6 = C.dig6_string()
if dig6 not in CC:
CC.add(dig6)
yield C
Have you looked if Nauty can help?
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.