Opened 12 years ago

Last modified 11 years ago

#6679 closed enhancement

[with patch, needs review] Vertex Coloring, Edge Coloring — at Version 11

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (14)

Changed 12 years ago by ncohen

First patch !

Changed 12 years ago by ncohen

First patch !

comment:1 Changed 12 years ago by 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 ;

comment:2 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:4 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 12 years ago by ncohen

  • Summary changed from [with patch, needs review] Vertex Coloring, Edge Coloring (uses Linear Programming) to [with patch, needs review] Vertex Coloring, Edge Coloring

comment:7 Changed 12 years ago by ncohen

  • Summary changed from [with patch, needs review] Vertex Coloring, Edge Coloring to [with patch, needs work] Vertex Coloring, Edge Coloring

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

comment:8 Changed 11 years ago by ncohen

  • Description modified (diff)
  • Summary changed from [with patch, needs work] Vertex Coloring, Edge Coloring to [with patch, needs review] Vertex Coloring, Edge Coloring

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 !!!!

Changed 11 years ago by ncohen

comment:9 Changed 11 years ago by kcrisman

  • Status changed from needs_review to needs_info

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.

comment:10 Changed 11 years ago by ncohen

  • Status changed from needs_info to needs_review

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

comment:11 Changed 11 years ago by ncohen

  • Description modified (diff)
Note: See TracTickets for help on using tickets.