Revision history [back]

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([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            else:
                G.delete_edge(E[e])
            yield G

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([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            else:
                G.delete_edge(E[e])
            yield G

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([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            else:
                G.delete_edge(E[e])
            yield G

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([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            else:
                G.delete_edge(E[e])
            yield G

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

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([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            else:
                G.delete_edge(E[e])
            C = G.canonical_label().copy(immutable=True)
            if C not in CC:
                CC.add(C)
                yield C

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([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            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:
                CC.add(C)
CC.add(dig6)
                yield C

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

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