Opened 12 years ago
Last modified 11 years ago
#6679 closed enhancement
[with patch, needs review] Vertex Coloring, Edge Coloring — at Version 8
| 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 )
Hello everybody !!!
Here are two new functions for the Graph class in Sage : vertex_coloring and edge_coloring.
Those new functions both use Linear programming, so to use them you will have to install the patch for the class numerical.MIP in #6869 along with GLPK or CBC ( see # 6869 )
I hope I learned what I had to with my previous patch, as I hope you will find those functions sufficiently and correctly documented. These functions should be ---way--- more efficient than the previous ones, regardless of the Linear Solver you chose to use.
Change History (11)
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 !!!!
First patch !