#7184: [with patch, needs work] Implement counting of spanning trees for graphs
and digraphs + some fixing in kirchhoff_matrix
----------------------------+-----------------------------------------------
Reporter: AJonsson | Owner: rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.2
Component: graph theory | Keywords:
Work_issues: | Author:
Reviewer: | Merged:
----------------------------+-----------------------------------------------
Comment(by ncohen):
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7184#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
