#6679: [with patch, needs review] Vertex Coloring, Edge Coloring
----------------------------+-----------------------------------------------
Reporter: ncohen | 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):
* status: needs_info => needs_review
Comment:
Hello !!!!
I wrote this patch some time ago, and it needed an update because of some
changes in class numerical.mip. Besides, your sound remark needs an answer
:-)
Here is what this new version of the patch does :
* It creates two functions vertex_coloring and edge_coloring in the
graph_coloring module.
* I noticed there were methods defined in the graph_coloring module
which were not used in the Graph class, even though they
were built just for that ! For example, the function
Graph.chromatic_number computes the chromatic number through computing the
whole Chromatic Polynomial (honestly, I do not know any worse way to
compute it !), even though there is a chromnatic_number function in the
graph_coloring module computing the same parameter with a different
method. I updated the Graph.chromatic_number method to let the user chose
one of the (now three) different ways to compute the chromatic polynomial.
I set it to MILP by default ( so that it uses the new vertex_coloring
method which is defined in this patch ) as I expect it to be the most
efficient.
* The same thing occured in the Graph.coloring() function. This method
used a slower version of what was already available in the graph_coloring
module. It now uses the graph_coloring.first_coloring method, or the
newly defined vertex_coloring method.
* Functions graph_coloring.chromatic_number and
graph_coloring.first_coloring compute things that can also be computed
through the use of the newly created graph_coloring.vertex_coloring
method. I think the way they compute their results is far too slow, as
they compute ALL the colorings to return one, and so should be removed (
the function all_graph_colorings, which they all use, must obvously be
kept ) some months from now, while they should be kept some time to
compare their results with graph_coloring.vertex_coloring ( both speed and
exactness )
* Several docstring fixes, when I noticed them
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6679#comment:10>
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
-~----------~----~----~----~------~----~------~--~---
