Sage: Ticket #7184: Implement counting of spanning trees for graphs and digraphs
https://trac.sagemath.org/ticket/7184
<p>
This patch allows us to count the number of spanning trees in a simple graph, as well as the spanning out-trees from a user-defined root node in a digraph.
</p>
<p>
Method used: Kirchhoff's matrix tree theorem [1] and the Laplacian matrix for the simple graphs, and a variation of the same [2] in the directed case.
</p>
<p>
[1] <a class="ext-link" href="http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem"><span class="icon"></span>http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem</a> <br />
[2] corollary 4.4 in <a class="ext-link" href="http://books.google.se/books?id=vbxdqhDKOSYC&printsec=frontcover&hl=en&source=gbs_navlinks_s"><span class="icon"></span>http://books.google.se/books?id=vbxdqhDKOSYC&printsec=frontcover&hl=en&source=gbs_navlinks_s</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7184
Trac 1.1.6AJonssonSat, 10 Oct 2009 18:00:46 GMTattachment set
https://trac.sagemath.org/ticket/7184
https://trac.sagemath.org/ticket/7184
<ul>
<li><strong>attachment</strong>
set to <em>trac_7184.patch</em>
</li>
</ul>
<p>
count spanning trees of graphs
</p>
TicketAJonssonSat, 10 Oct 2009 18:03:00 GMTdescription changed
https://trac.sagemath.org/ticket/7184#comment:1
https://trac.sagemath.org/ticket/7184#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/7184?action=diff&version=1">diff</a>)
</li>
</ul>
TicketAJonssonSat, 10 Oct 2009 18:05:43 GMTstatus changed
https://trac.sagemath.org/ticket/7184#comment:2
https://trac.sagemath.org/ticket/7184#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketncohenSun, 18 Oct 2009 12:16:29 GMTsummary changed; cc set
https://trac.sagemath.org/ticket/7184#comment:3
https://trac.sagemath.org/ticket/7184#comment:3
<ul>
<li><strong>cc</strong>
<em>boothby</em> added
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Implement counting of spanning trees for graphs and digraphs</em> to <em>[with patch, needs review] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix</em>
</li>
</ul>
<p>
Here is a new patch based on yours, plus some modifications :
</p>
<ul><li>I was not able at first to apply your patch, as it was based on an old version of Sage. This new version is now based on 4.1.2.rc0.
</li><li>I fixed some docstrings :
<ul><li>you set "math" mode with this sign : `
( exemple : <code>x^2</code> )
</li><li>you set "sage" mode with this sign : <code></code>
( exemple : <code></code>graph.am()<code></code> )
</li></ul></li><li>I renamed the function from spanning_trees to spanning_tree_count as the first seemed to imply an iterator over spanning_trees
</li><li>Some details concerning the root_vertex too. Many graphs have vertices not among integers but among strings, or tuples, etc. Besides, it is not necessary to enumerate all the vertices to get the first one :
<pre class="wiki">v=G.vertices()[0]
</pre>You can also do :
<pre class="wiki">v=G.vertex_iterator().next()
</pre></li><li>You had to modify the adjacency matrix to fit the definition used in your references. This was perfectly fine, but also meant there was an error in the definition of <code></code>kirchhoff_matrix<code></code> for directed graph. This patch fixes this, plus some docstrings error in the kirchhoff_matrix function.
</li></ul><p>
Short of these details, you algorithm works fine, thank you for having sent this patch !!
</p>
<p>
If you agree with this nex patch I am sending, you can set this ticket to positive_review
</p>
<p>
Thanks !
</p>
<p>
Nathann
</p>
<p>
Algorithm is OK, both for Graphs and Digraphs. You had to re-define
</p>
TicketncohenSun, 18 Oct 2009 12:18:29 GMT
https://trac.sagemath.org/ticket/7184#comment:4
https://trac.sagemath.org/ticket/7184#comment:4
<p>
Ooops, sorry for the last line, which was not meant to be included in my message. Besides, I meant that you had to redefine the kirchhoff matrix, not the adjacency matrix.. Sorry :-)
</p>
TicketboothbySun, 18 Oct 2009 17:10:02 GMTsummary changed
https://trac.sagemath.org/ticket/7184#comment:5
https://trac.sagemath.org/ticket/7184#comment:5
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix</em> to <em>[with patch, needs work] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix</em>
</li>
</ul>
<p>
Ncohen, you've broken kirchhoff_matrix. According to the definition, row-sums of the Kirchhoff matrix should be zero. Here's the doctest before you changed it:
</p>
<pre class="wiki">sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True)
sage: G.laplacian_matrix()
[ 3 -3]
[-4 4]
</pre><p>
here, the row-sums are zero.
</p>
<p>
But you actually had to change the doctest to make the code pass,
</p>
<pre class="wiki">sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True)
sage: G.laplacian_matrix()
[ 4 -3]
[-4 3]
</pre><p>
but the row-sums aren't zero! Don't break math to make code work!
</p>
TicketboothbySun, 18 Oct 2009 17:10:12 GMTstatus changed
https://trac.sagemath.org/ticket/7184#comment:6
https://trac.sagemath.org/ticket/7184#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketncohenSun, 18 Oct 2009 17:42:25 GMT
https://trac.sagemath.org/ticket/7184#comment:7
https://trac.sagemath.org/ticket/7184#comment:7
<p>
Hello !!
</p>
<p>
Yes, I indeed changed the docstring because I thought this was a bug in kirchoff_matrix. As it is written in the patch I sent, the definition of kirchhoff matrix perfectly matches the definition from <a class="ext-link" href="http://en.wikipedia.org/wiki/Laplacian_matrix"><span class="icon"></span>http://en.wikipedia.org/wiki/Laplacian_matrix</a>
Two differences : the kirchhoff matrix can be defined when the graph is a <a class="missing wiki">DiGraph?</a>.
</p>
<ul><li>In this case, as defined ( for example ) in the book AJonsson is mentionning, the diagonal values should be set to the indegree of each vertex ( and not their out-degree as it is currenty the case ). He has, in his own code, to change manually the values from the returned kirchhoff_matrix, which I felt was not right if the kirchhoff_matrix function was "correctly" defined ( "correctly" here means : according to this book ).
</li><li>In this docstring, you test your code against a special graph, as it has loops. As you see, the definition from wikipedia does not include the case where the graph includes loops. The definition from the book AJonsson mentions in his docstring ( I have it as a pdf file and can send it to you if you like ) produces the output of the functions kirchoff_matrix when my patch is applied.
</li></ul><p>
I honestly thought this was just a bug happening in special cases ( <a class="missing wiki">DiGraph?</a> + loops ), and checked several times the definition. Could you tell me which one you used ?
</p>
<p>
Sorry for the trouble. In added you in Cc uniquely to avoid unnoticed changes like this. Oh, and btw, I ran sage -testall to be sure this modifications broke no part of Sage.
</p>
<p>
Nathann
</p>
TicketAJonssonMon, 19 Oct 2009 19:48:00 GMTstatus changed
https://trac.sagemath.org/ticket/7184#comment:8
https://trac.sagemath.org/ticket/7184#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hello Nathann,
thanks for your review. I agree with your changes and have made an updated patch against sage 4.1.2. I did some more testing and noticed that the code for digraphs could easily be crashed by adding string-labeled vertices, so added a type check for that.<br />
</p>
<p>
As for the Laplacian matrix, I left the current function alone since I saw the following on wikipedia: "In the case of directed graphs, either the indegree or the outdegree might be used [for the diagonal values], depending on the application." At the present only the out-degree is used in sage, but it would of course be possible to make it a user option at creation of the Laplacian matrix if in- or out-degrees are to be used.
</p>
TicketAJonssonMon, 19 Oct 2009 19:49:27 GMTattachment set
https://trac.sagemath.org/ticket/7184
https://trac.sagemath.org/ticket/7184
<ul>
<li><strong>attachment</strong>
set to <em>trac_7184-try2.patch</em>
</li>
</ul>
<p>
built against sage 4.1.2, extra typecheck
</p>
TicketncohenMon, 19 Oct 2009 20:19:48 GMTstatus, summary changed
https://trac.sagemath.org/ticket/7184#comment:9
https://trac.sagemath.org/ticket/7184#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix</em> to <em>Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix</em>
</li>
</ul>
<p>
Considering the view Tom Boothby had of my little modification of kirchhoff_matrix, it may be better not to touch it for the moment in this patch. If as you say, the two different ways are used, the best option would be to modify kirchhoff_matrix as you say, to let the user choose its own definition. ( the problem with the loops still remains, though, but we do not really care about it in this special application ).
</p>
<p>
I am still worried about what you said considering Strings, though. If as you say, your code can be broken if vertices are strings, then you did not really solve your problem by taking this into account, as vertices can actually be of any immutable type. See for example patch <a class="closed ticket" href="https://trac.sagemath.org/ticket/7246" title="enhancement: digraph.DeBruijn in graph_generators (closed: fixed)">#7246</a> where vertices are defined as Words ( which is a totally independent Sage object ). This does not fit in the integer case, nor in the String case.
</p>
<p>
If I make no mistake remembering what is written in the book you mentioned, they also talk of a different way to compute the number of out-trees : you do not add this special vertex, but just consider the kirchhoff matrix of the first graph, then add 1 to the vertex you want to take as root. It is ( I think ) an easier way to define your matrix in this case, without having to consider these types.. You just have to deal with the matrix ! ( I'm sorry I can not write this patch myself now, I do not have the correct tools on the computer I use and have some urgent work to get done until tomorrow... :-) )
</p>
<p>
Nathann
</p>
TicketAJonssonTue, 20 Oct 2009 17:02:54 GMTstatus, summary changed
https://trac.sagemath.org/ticket/7184#comment:10
https://trac.sagemath.org/ticket/7184#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>summary</strong>
changed from <em>Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix</em> to <em>Implement counting of spanning trees for graphs and digraphs</em>
</li>
</ul>
<p>
Hello Nathann, thanks for pointing me in the right way, I have made a new patch that just increases the diagonal value of the root vertex by 1, which indeed is a simpler solution. As a bonus there is no longer any need to copy the graph, since we no longer do any changes to the original graph in our computations.
</p>
<p>
Anders
</p>
TicketboothbyWed, 21 Oct 2009 01:13:37 GMT
https://trac.sagemath.org/ticket/7184#comment:11
https://trac.sagemath.org/ticket/7184#comment:11
<p>
Nathann, I was wrong! I've ONLY dealt with Kirchhoff matrices in the context of electrical networks, in which loops are utterly insignificant. For me, the definition of the Kirchhoff matrix is that the diagonal is the row-sum of the weighted adjacency matrix. But, the definition you are using appears to be standard, and as noted here, more useful.
</p>
TicketncohenWed, 21 Oct 2009 10:07:16 GMT
https://trac.sagemath.org/ticket/7184#comment:12
https://trac.sagemath.org/ticket/7184#comment:12
<p>
This patch should satisfy all of us, I hope. It includes the last version of AJonsson's code, and it adds an argument to kirchhoff_matrix so that the user may chose if D is the matrix of indegree or outdegrees.
</p>
<p>
I added the corresponding documentation to the kirchhoff_matrix function.
</p>
<p>
I have to mention that the way kirchhoff_matrix is written contains a lot of repetitions because of the possibility of different values for the indegree variable. I thought of other ways to write it to preserve the code, but these ways could have at some point impaired the performances, as checks for the values of the variable indegree could have happened much more often. I write it this way as the function is still very short and this should not be a problem for its maintenance.
</p>
<p>
Oh, and the patch is based on 4.1.2.rc0
</p>
<p>
Nathann
</p>
TicketAJonssonWed, 21 Oct 2009 12:07:08 GMT
https://trac.sagemath.org/ticket/7184#comment:13
https://trac.sagemath.org/ticket/7184#comment:13
<p>
Looks fine to me. With your patch applied there is another line in count_spanning_trees that no longer is needed. Apply this patch on top of trac_7184-reviewer.patch to remove that line.
</p>
TicketAJonssonWed, 21 Oct 2009 12:08:38 GMTattachment set
https://trac.sagemath.org/ticket/7184
https://trac.sagemath.org/ticket/7184
<ul>
<li><strong>attachment</strong>
set to <em>trac7184-simplified.patch</em>
</li>
</ul>
<p>
remove unneeded reassignment of all diagonal entries of Kirchhoff matrix
</p>
TicketncohenWed, 21 Oct 2009 12:55:17 GMT
https://trac.sagemath.org/ticket/7184#comment:14
https://trac.sagemath.org/ticket/7184#comment:14
<p>
Sorryyyyyyy !! I had forgotten to edit your function after I edited kirchhoff_matrix !
</p>
<p>
Here is a new patch removing this line which is now integrated into kirchhoff_matrix. Besides, I wanted to do something about
</p>
<pre class="wiki"> for i in self.vertices():
M[j,j]=self.in_degree(i)
if (self.vertices()[j]== root_vertex):
M[j,j]= M[j,j] + 1
j= j + 1
</pre><p>
With these lines, you are evaluating all the vertices at each look, just to return its jth element. As the vertices do not change, you could have stored the list of vertices in a variable, each time trying to find the jth element of this list ( without listing allt he vertices again ). But with this new patch, you are just getting the index of the vertex you are interested in, and updating the matrix... And with some luck, this patch is the last one :-)
</p>
TicketncohenWed, 21 Oct 2009 12:55:41 GMTattachment set
https://trac.sagemath.org/ticket/7184
https://trac.sagemath.org/ticket/7184
<ul>
<li><strong>attachment</strong>
set to <em>trac_7184-reviewer.patch</em>
</li>
</ul>
TicketAJonssonWed, 21 Oct 2009 14:37:28 GMT
https://trac.sagemath.org/ticket/7184#comment:15
https://trac.sagemath.org/ticket/7184#comment:15
<p>
Looks really nice. I'm fully satisfied with the patch.
</p>
<p>
Anders
</p>
TicketncohenThu, 22 Oct 2009 08:04:50 GMT
https://trac.sagemath.org/ticket/7184#comment:16
https://trac.sagemath.org/ticket/7184#comment:16
<p>
Do we both agree on a positive review, then ? ;-)
</p>
TicketncohenMon, 26 Oct 2009 07:03:05 GMTstatus changed
https://trac.sagemath.org/ticket/7184#comment:17
https://trac.sagemath.org/ticket/7184#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Well, I'll take your "Looks really nice. I'm fully satisfied with the patch" as as an answer :-)
</p>
TicketboothbyMon, 26 Oct 2009 23:01:30 GMTstatus, summary changed
https://trac.sagemath.org/ticket/7184#comment:18
https://trac.sagemath.org/ticket/7184#comment:18
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>summary</strong>
changed from <em>Implement counting of spanning trees for graphs and digraphs</em> to <em>Implement counting of spanning trees for graphs and digraphs [with patch, needs review]</em>
</li>
</ul>
<p>
Sorry guys, reviewers need to not touch the code. Rather... authors can't give the final +1.
</p>
TicketboothbyMon, 26 Oct 2009 23:01:39 GMTstatus changed
https://trac.sagemath.org/ticket/7184#comment:19
https://trac.sagemath.org/ticket/7184#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketmhansenMon, 07 Dec 2009 08:47:33 GMTstatus changed; author, upstream, reviewer, resolution, merged set
https://trac.sagemath.org/ticket/7184#comment:20
https://trac.sagemath.org/ticket/7184#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>closed</em>
</li>
<li><strong>author</strong>
set to <em>Anders Jonsson, Nathann Cohen</em>
</li>
<li><strong>upstream</strong>
set to <em>N/A</em>
</li>
<li><strong>reviewer</strong>
set to <em>Mike Hansen</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.3.rc0</em>
</li>
</ul>
<p>
Looks good to me.
</p>
TicketmvnguSat, 26 Dec 2009 19:12:07 GMTsummary changed
https://trac.sagemath.org/ticket/7184#comment:21
https://trac.sagemath.org/ticket/7184#comment:21
<ul>
<li><strong>summary</strong>
changed from <em>Implement counting of spanning trees for graphs and digraphs [with patch, needs review]</em> to <em>Implement counting of spanning trees for graphs and digraphs</em>
</li>
</ul>
Ticket