[with patch, needs review] Vertex Coloring, Edge Coloring

[ncohen]

Hello everybody !!!

Here are two new functions for the Graph class in Sage : vertex_coloring and edge_coloring.

If you have no LP Solver installed, you can download GLPK or CBC from this address : http://www.sagemath.org/packages/optional/

These functions should be ---way--- more efficient than the previous ones, regardless of the Linear Solver you chose to use.

[ncohen]

First patch !

[ncohen]

First patch !

[ncohen]

Hmmm... The two patches coloring-1 and coloring-1.2 are exactly identical, but I do not know how to remove the second one ;

[ncohen]

As the functions dealing with LP have not been reviewed, I prefer to rewrite the MIP class for Sage to make it easier to use. I will post a new version of the MIP patch as soon as possible, along with all the patches for functions using it.

Sorry for the trouble, I'll try to make it quick !

Nathann

[ncohen]

Even shorter, even better, even more efficient... Here is the new version of these two functions, now using the symbolic version of MIP from #6869 !!!!

[kcrisman]

I have a question. What is the relation to the already existing methods .chromatic_number() and .coloring()?

sage: G = graphs.PetersenGraph()
sage: G.coloring()
[[1, 3, 5, 9], [0, 2, 6], [4, 7, 8]]
sage: G.chromatic_number()
3

At the very least it seems reasonable to modify .coloring() rather than add a new function, and perhaps keep the previous algorithm if that is useful. I can't speak to which one is better, unfortunately, but it can be good to avoid a surfeit of methods.

[ncohen]

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