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: |
Description (last modified by )
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
comment:1 Changed 12 years ago by
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
- Description modified (diff)
comment:3 Changed 12 years ago by
- Description modified (diff)
comment:4 Changed 12 years ago by
- Description modified (diff)
comment:5 Changed 12 years ago by
- Description modified (diff)
comment:6 Changed 12 years ago by
- 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
- 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
- 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
comment:9 Changed 11 years ago by
- 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
- 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
- Description modified (diff)
First patch !