#7184: [with patch, needs review] Implement counting of spanning trees for
graphs
and digraphs + some fixing in kirchhoff_matrix
----------------------------+-----------------------------------------------
Reporter: AJonsson | Owner: rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.2
Component: graph theory | Keywords:
Work_issues: | Author:
Reviewer: | Merged:
----------------------------+-----------------------------------------------
Changes (by ncohen):
* cc: boothby (added)
Comment:
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()`` )
* 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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7184#comment:3>
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
-~----------~----~----~----~------~----~------~--~---
