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/Random orientation of a graphhttps://ask.sagemath.org/question/42274/random-orientation-of-a-graph/ Is there a command to randomly orient a graph? (no additional edges) not the to_directed commandstandardtrickynessMon, 07 May 2018 02:36:46 +0200https://ask.sagemath.org/question/42274/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/Is there a way to compute the list of rooted spanning trees or arborescences in a directed graph ?https://ask.sagemath.org/question/37274/is-there-a-way-to-compute-the-list-of-rooted-spanning-trees-or-arborescences-in-a-directed-graph/Given a directed graph $D$ and a specified vertex $r$, I would like the list of all directed spanning trees, or arborescences, rooted in $r$.
This can be computed by induction as is done for spanning trees in undirected graphs with the *spanning_trees* method of the class *Graph*, but it seems like this has not been implemented for directed graphs.David AugerThu, 13 Apr 2017 10:12:24 +0200https://ask.sagemath.org/question/37274/Mixed graphhttps://ask.sagemath.org/question/36938/mixed-graph/ Can we draw mixed graphs( graphs with some edges oriented while some are not) in sagemath?
Deepak SarmaTue, 14 Mar 2017 05:16:39 +0100https://ask.sagemath.org/question/36938/to_directed() affects original graphhttps://ask.sagemath.org/question/36705/to_directed-affects-original-graph/ I've stumbled on what I think is a bug. When you create a directed graph from some original graph and then making changes on the new, this can affect the old one. I'm not sure if it should be like this and one should always copy the graph first. Here's a minimal example that for be gives an error "KeyError: 0".
G1=graphs.RandomGNP(5,0.5)
G1.plot(save_pos=True)
G2=G1.to_directed()
G2.delete_vertex(0)
G2.add_vertex(5)
G2.plot()
G1.plot()AckslThu, 23 Feb 2017 11:27:23 +0100https://ask.sagemath.org/question/36705/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/How to get an arbitrary orientation of a graph.https://ask.sagemath.org/question/34711/how-to-get-an-arbitrary-orientation-of-a-graph/I want to know how to get the iterator of all orientations of a given graph G.
Thanks for your valuable timing.
There is another question in the same title, unfortunately that question has irrelevant title.
https://ask.sagemath.org/question/9835/how-to-get-an-arbitrary-orientation-of-a-graph/GA316Sun, 04 Sep 2016 07:59:18 +0200https://ask.sagemath.org/question/34711/Finding number of strongly connected componentshttps://ask.sagemath.org/question/33735/finding-number-of-strongly-connected-components/I need to find the number of strongly connected components of a digraph, and I looked at the documentation for the ~DiGraph.strongly_connected_components() method. Tabbing .strongly_connected_components? gives the documentation from sage/graphs/base/static_sparse_graph.pyx for tarjan_strongly_connected_components(G) that says,
This routine returns a pair ``[nscc, scc]``, where ``nscc`` is the number of
SCCs and ``scc`` is a dictionary associating to each vertex ``v`` an
integer between ``0`` and ``nscc-1``, corresponding to the SCC containing
``v``. SCCs
are numbered in reverse topological order, that is, if ``(v,w)`` is an edge
in the graph, ``scc[v] <= scc[w]``
Which would be great, as I just need the result of tarjan_strongly_connected_components_C. However, 1) this is only called during tarjan_strongly_connected_components, which does the (admittedly minor) additional work of topologically sorting SCCs and 2) the examples (and testing) show the output of ~DiGraph.strongly_connected_components() is a list of vertex lists for each connected component. This is perfectly reasonable and clear, but more than I want, particularly as there's some work in the back end that determines what I'm looking for earlier in the process.
1) Should I just use len(~DiGraph.strongly_connected_components())?
2) Am I badly misreading the documentation for this method?
I'm in Sage 7.2.
Thanks in advance for help here!JEFLSUFri, 10 Jun 2016 15:01:31 +0200https://ask.sagemath.org/question/33735/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/hasse diagram of a subset of a posethttps://ask.sagemath.org/question/29791/hasse-diagram-of-a-subset-of-a-poset/E = {1,2,3}
P = SetPartitions(E)
This gives the set of all partitions of E,.
I have a subset Q of P and I want to construct the directed graph whose vertex set is this set Q and we draw an arrow from p to q in this graph if q covers p. How to construct this graph for a given P and Q?
The definition of covering relation can be found here : https://en.wikipedia.org/wiki/Covering_relation
Thanks for your valuable timing.GA316Tue, 06 Oct 2015 15:39:38 +0200https://ask.sagemath.org/question/29791/Eulerian Cycle of a Digraphhttps://ask.sagemath.org/question/7844/eulerian-cycle-of-a-digraph/Hello,
Is there a function to do an Eulerian cycle of a digraph? eulerian_cycle works on undirected graphs, but not on digraphs. Basically I'm looking for an equivalent to Mathematica's EulerianCycle. Does this exist?
Thanks in advance.Eviatar BachThu, 06 Jan 2011 20:43:08 +0100https://ask.sagemath.org/question/7844/