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.Fri, 14 Apr 2017 21:04:37 +0200Is 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.Thu, 13 Apr 2017 10:12:24 +0200https://ask.sagemath.org/question/37274/is-there-a-way-to-compute-the-list-of-rooted-spanning-trees-or-arborescences-in-a-directed-graph/Answer by tmonteil for <p>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 <em>spanning_trees</em> method of the class <em>Graph</em>, but it seems like this has not been implemented for directed graphs.</p>
https://ask.sagemath.org/question/37274/is-there-a-way-to-compute-the-list-of-rooted-spanning-trees-or-arborescences-in-a-directed-graph/?answer=37299#post-id-37299Indeed, it seems there is no method for enumerating spanning trees on digraphs (though there is a `spanning_trees_count` method for counting them based on the Kirchhoff matrix). If you have an implementation, let me suggest to add it into Sage itself, see http://www.sagemath.org/development.html
Fri, 14 Apr 2017 21:04:37 +0200https://ask.sagemath.org/question/37274/is-there-a-way-to-compute-the-list-of-rooted-spanning-trees-or-arborescences-in-a-directed-graph/?answer=37299#post-id-37299