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/How to get all digraphs with loopshttps://ask.sagemath.org/question/35736/how-to-get-all-digraphs-with-loops/ I'm trying to count all of the directed graphs on n vertices which have fixed in/out degree, up to isomorphism. I would like to allow loops, though not multiple edges. I can't figure out how to tell the digraphs iterrator to include the ones with loops, though i see this is an option in the graphs iterator. I would appreciate suggestions to get around this/explanations why it is not an option.BillyFri, 25 Nov 2016 10:30:55 +0100https://ask.sagemath.org/question/35736/Using a lambda expression in digraphs fails for len(G.sinks())?https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/I'm gathering digraphs that have exactly one sink.
This list comprehension works fine to find the 6 such digraphs of order 3 & put them in a list:
[G for G in digraphs(3) if len(G.sinks()) == 1]
However, I need this to work in a lambda expression to make it part of a larger calculation. However,
digraphs(3,lambda G: len(G.sinks()) == 1)
creates an iterator that returns no entries.
Creating a lamba expression creates the same unexpected zero-length iterator in digraphs, but that same iterator correctly finds the 6 single-sink digraphs if used in a for expression:
sage: property = lambda G: len(G.sinks()) == 1
sage: T = digraphs(3, property)
sage: print(list(T))
[]
sage: for H in digraphs(3):
....: print property(H)
....:
False
False
False
True
False
False
False
False
True
True
True
True
False
True
False
False
So, what's the right way to generate the one-sink digraphs of order N directly in the digraphs() generator?
jim_snydergrantThu, 12 May 2016 17:05:40 +0200https://ask.sagemath.org/question/33384/