#7184 closed enhancement (fixed)
Implement counting of spanning trees for graphs and digraphs
Reported by: | AJonsson | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3 |
Component: | graph theory | Keywords: | |
Cc: | boothby | Merged in: | sage-4.3.rc0 |
Authors: | Anders Jonsson, Nathann Cohen | Reviewers: | Mike Hansen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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.
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.
[1] http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem
[2] corollary 4.4 in http://books.google.se/books?id=vbxdqhDKOSYC&printsec=frontcover&hl=en&source=gbs_navlinks_s
Attachments (4)
Change History (25)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 10 years ago by
- Status changed from new to needs_review
comment:3 Changed 10 years ago by
- Cc boothby added
- Summary changed from [with patch, needs review] Implement counting of spanning trees for graphs and digraphs to [with patch, needs review] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix
Here is a new patch based on yours, plus some modifications :
- 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.
- I fixed some docstrings :
- you set "math" mode with this sign : `
( exemple :
x^2
) - you set "sage" mode with this sign :
( exemple :
graph.am()
)
- you set "math" mode with this sign : `
( exemple :
- I renamed the function from spanning_trees to spanning_tree_count as the first seemed to imply an iterator over spanning_trees
- 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 :
v=G.vertices()[0]
You can also do :v=G.vertex_iterator().next()
- 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
kirchhoff_matrix
for directed graph. This patch fixes this, plus some docstrings error in the kirchhoff_matrix function.
Short of these details, you algorithm works fine, thank you for having sent this patch !!
If you agree with this nex patch I am sending, you can set this ticket to positive_review
Thanks !
Nathann
Algorithm is OK, both for Graphs and Digraphs. You had to re-define
comment:4 Changed 10 years ago by
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 :-)
comment:5 Changed 10 years ago by
- Summary changed from [with patch, needs review] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix to [with patch, needs work] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix
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:
sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix() [ 3 -3] [-4 4]
here, the row-sums are zero.
But you actually had to change the doctest to make the code pass,
sage: G = DiGraph({1:{1:2,2:3}, 2:{1:4}}, weighted=True,sparse=True) sage: G.laplacian_matrix() [ 4 -3] [-4 3]
but the row-sums aren't zero! Don't break math to make code work!
comment:6 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:7 Changed 10 years ago by
Hello !!
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 http://en.wikipedia.org/wiki/Laplacian_matrix Two differences : the kirchhoff matrix can be defined when the graph is a DiGraph?.
- 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 ).
- 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.
I honestly thought this was just a bug happening in special cases ( DiGraph? + loops ), and checked several times the definition. Could you tell me which one you used ?
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.
Nathann
comment:8 Changed 10 years ago by
- Status changed from needs_work to needs_review
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.
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.
comment:9 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Summary changed from [with patch, needs work] Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix to Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix
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 ).
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 #7246 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.
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... :-) )
Nathann
comment:10 Changed 10 years ago by
- Status changed from needs_work to needs_review
- Summary changed from Implement counting of spanning trees for graphs and digraphs + some fixing in kirchhoff_matrix to Implement counting of spanning trees for graphs and digraphs
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.
Anders
comment:11 Changed 10 years ago by
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.
comment:12 Changed 10 years ago by
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.
I added the corresponding documentation to the kirchhoff_matrix function.
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.
Oh, and the patch is based on 4.1.2.rc0
Nathann
comment:13 Changed 10 years ago by
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.
comment:14 Changed 10 years ago by
Sorryyyyyyy !! I had forgotten to edit your function after I edited kirchhoff_matrix !
Here is a new patch removing this line which is now integrated into kirchhoff_matrix. Besides, I wanted to do something about
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
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 :-)
Changed 10 years ago by
comment:15 Changed 10 years ago by
Looks really nice. I'm fully satisfied with the patch.
Anders
comment:16 Changed 10 years ago by
Do we both agree on a positive review, then ? ;-)
comment:17 Changed 10 years ago by
- Status changed from needs_review to positive_review
Well, I'll take your "Looks really nice. I'm fully satisfied with the patch" as as an answer :-)
comment:18 Changed 10 years ago by
- Status changed from positive_review to needs_work
- Summary changed from Implement counting of spanning trees for graphs and digraphs to Implement counting of spanning trees for graphs and digraphs [with patch, needs review]
Sorry guys, reviewers need to not touch the code. Rather... authors can't give the final +1.
comment:19 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:20 Changed 10 years ago by
- Merged in set to sage-4.3.rc0
- Report Upstream set to N/A
- Resolution set to fixed
- Reviewers set to Mike Hansen
- Status changed from needs_review to closed
Looks good to me.
comment:21 Changed 10 years ago by
- Summary changed from Implement counting of spanning trees for graphs and digraphs [with patch, needs review] to Implement counting of spanning trees for graphs and digraphs
count spanning trees of graphs