# Revision history [back]

### 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?

from sage.combinat.gray_codes import product as gc_product
def Dags(n):
for P in Posets(n):
H = P.hasse_diagram()
E = [(v,u) for v in P for u in set(P.principal_upper_set(v))-set(H.neighbors_out(v))-{v}]
G = H.copy()
for e,d in gc_product(*len(E)):
if d>0:
else:
G.delete_edge(E[e])
yield G


### 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?

from sage.combinat.gray_codes import product as gc_product
def Dags(n):
for P in Posets(n):
H = P.hasse_diagram()
E = [(v,u) for v in P for u in set(P.principal_upper_set(v))-set(H.neighbors_out(v))-{v}]
G = H.copy()
yield G
for e,d in gc_product(*len(E)):
if d>0:
else:
G.delete_edge(E[e])
yield G


### 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?

from sage.combinat.gray_codes import product as gc_product
def Dags(n):
for P in Posets(n):
H = P.hasse_diagram()
E = [(v,u) for v in P for u in set(P.principal_upper_set(v))-set(H.neighbors_out(v))-{v}]
list( set(H.transitive_closure().edges()) - set(H.edges()) )
G = H.copy()
yield G
for e,d in gc_product(*len(E)):
if d>0:
else:
G.delete_edge(E[e])
yield G 4 retagged

### 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?

from sage.combinat.gray_codes import product as gc_product
def Dags(n):
for P in Posets(n):
H = P.hasse_diagram()
E = list( set(H.transitive_closure().edges()) - set(H.edges()) )
G = H.copy()
yield G
for e,d in gc_product(*len(E)):
if d>0:
else:
G.delete_edge(E[e])
yield G


### 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 Dags(n):
for P in Posets(n):
H = P.hasse_diagram()
E = list( set(H.transitive_closure().edges()) - set(H.edges()) )
G = H.copy()
C = G.canonical_label().copy(immutable=True)
CC = set(C)
yield G
C
for e,d in gc_product(*len(E)):
if d>0:
else:
G.delete_edge(E[e])
C = G.canonical_label().copy(immutable=True)
if C not in CC:
yield G
C


### 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 Dags(n):
for P in Posets(n):
H = P.hasse_diagram()
E = list( set(H.transitive_closure().edges()) set(H.transitive_closure().edges(labels=False)) - set(H.edges()) set(H.edges(labels=False)) )
G = H.copy()
C = G.canonical_label().copy(immutable=True)
CC = set(C)
yield C
for e,d in gc_product(*len(E)):
if d>0:
else:
G.delete_edge(E[e])
C = G.canonical_label().copy(immutable=True)
if C not in CC:
yield C


### 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 Dags(n):
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().copy(immutable=True)
G.canonical_label()
CC = set(C)
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().copy(immutable=True)
G.canonical_label()
dig6 = C.dig6_string()
if C dig6 not in CC:
yield C


### 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: