Revision history [back]

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(1,7)]
[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(1,7)]                                                                                                                                                               
[1, 2, 6, 31, 302, 5984]

It is unfortunately slower than your method.

For more details about the digraphs function, see:

sage: digraphs?

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(1,7)]
[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(1,7)]                                                                                                                                                               
[1, 2, 6, 31, 302, 5984]

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

For more details about the digraphs function, see:

sage: digraphs?

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(1,7)]
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(1,7)] 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?