ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 16 Mar 2021 21:23:41 +0100iterate over all directed acyclic graphs (DAGs) on n verticeshttps://ask.sagemath.org/question/56190/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 CMax AlekseyevTue, 16 Mar 2021 21:23:41 +0100https://ask.sagemath.org/question/56190/Iterate over acyclic subdigraphshttps://ask.sagemath.org/question/37611/iterate-over-acyclic-subdigraphs/I have a graph `D`, and would like to iterate over its (maximal) acyclic subdigraphs (not necessarily induced).
My current best bet is to iterate over all permutations of the vertex set of D and, for each one, create an acyclic digraph A by going through each edge of D in turn and adding to A only those edges `ij` where `i` is less than `j` in the current permutation.
But this seems awfully inefficient.
More precisely:
D = DiGraph()
D.add_edges([[0,1],[0,2],[1,2],[1,3],[2,3],[3,4],[4,5],[4,6],[5,6],[5,0],[6,0]])
n = D.num_verts()
for p in Permutations(n):
A = DiGraph()
for e in D.edges():
if p[e[0]] < p[e[1]]:
A.add_edge(p[e[0]] -1,p[e[1]] -1)
# Here A is a maximal acyclic subdigraph of D
do_stuff(A)
Any ideas would be greatly appreciated.tassioWed, 17 May 2017 17:34:11 +0200https://ask.sagemath.org/question/37611/