#7184: 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:
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7184#comment:9>
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
-~----------~----~----~----~------~----~------~--~---
