Ask Your Question
2

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

asked 2021-03-16 21:23:41 +0100

Max Alekseyev gravatar image

updated 2024-04-12 20:13:21 +0100

FrédéricC gravatar image

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
edit retag flag offensive close merge delete

Comments

Have you looked if Nauty can help?

slelievre gravatar imageslelievre ( 2021-03-18 22:13:00 +0100 )edit

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.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-03-18 22:44:05 +0100 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2021-03-17 23:11:19 +0100

tmonteil gravatar image

updated 2021-03-18 00:15:23 +0100

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?
edit flag offensive delete link more

Comments

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).

Max Alekseyev gravatar imageMax Alekseyev ( 2021-03-18 17:41:15 +0100 )edit

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.

tmonteil gravatar imagetmonteil ( 2021-03-18 18:00:18 +0100 )edit

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).

Max Alekseyev gravatar imageMax Alekseyev ( 2021-03-18 18:20:12 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-03-16 21:23:41 +0100

Seen: 323 times

Last updated: Mar 18 '21