Opened 11 years ago
Closed 10 years ago
#6679 closed enhancement (fixed)
Vertex Coloring, Edge Coloring
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.3.alpha1 | |
Authors: | Nathann Cohen | Reviewers: | Karl-Dieter Crisman, Minh Van Nguyen |
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.
DEPENDS ON #7270 !!!!!!!!!!!!!
Attachments (5)
Change History (24)
Changed 11 years ago by
comment:1 Changed 11 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 11 years ago by
- Description modified (diff)
comment:3 Changed 11 years ago by
- Description modified (diff)
comment:4 Changed 11 years ago by
- Description modified (diff)
comment:5 Changed 11 years ago by
- Description modified (diff)
comment:6 Changed 11 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 10 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 10 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 10 years ago by
comment:9 Changed 10 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 10 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 10 years ago by
- Description modified (diff)
comment:12 Changed 10 years ago by
Added round_robin, and a more efficient coloring for complete graphs
comment:13 Changed 10 years ago by
- Report Upstream set to N/A
- Status changed from needs_review to needs_work
- Summary changed from [with patch, needs review] Vertex Coloring, Edge Coloring to Vertex Coloring, Edge Coloring
I assume that the patch trac_6679.patch
is the one to review, so here goes. Here are some issues:
- For the function
chromatic_number()
, it's a bad idea to make "MILP" the default algorithm choice because that algorithm requires the installation of an optional package. Imagine the surprise (and confusion) when one uses the functionchromatic_number()
with the default value, but neither GLPK nor CBC is installed. You can make some algorithm a default choice provided that it's in a standard package or in the Sage library. If you have another algorithm that uses an optional package, you could still provide an interface to that algorithm and document uses of that algorithm in the docstring. So between "CP" and "DLX", choose one and make that algorithm the default choice. You have clearly documented how to use the "MILP" algorithm, which is good for those who want a better algorithm. - You don't need to put spaces between the sign "=" if it occurs as part of assigning a value to an argument in a function call, like in
chromatic_number(algorithm="MILP")
. To follow coding conventions, you should put spaces between operators. So instead of doingalgorithm=="CP"
, you should doalgorithm == "CP"
. You can read more about Python coding conventions in PEP 8. - Use the style of raising exceptions that is compatible with Python 3.x. For example, the following is not recommended for being compatible with Python 3.x:
raise ValueError, "The `algorithm` variable must be set to either `DLX`, `MILP` or `CP`."
However, the following style is compatible with Python 3.x:raise ValueError("The `algorithm` variable must be set to either `DLX`, `MILP` or `CP`.")
Lots of code in the Sage library still uses the old style of raising exceptions. This will come back to haunt us when the time comes to switch to Python 3.x. - The formatting of docstring is inconsistent.
comment:14 follow-up: ↓ 15 Changed 10 years ago by
Patch updated ! I also noticed I had forgotten one "optional" tag in the docstrings, and I rewrote all the ValueError? I was able to find in the whole file.
I have a question though : I build the reference to check the docstrings and noticed the file graph_colouring.pyx was not included in them : should we change it ?
There are still many "test" functions in this file that may not be of interest to the user, though....
In any case, thank you very much for your help :-)
Nathann
Changed 10 years ago by
comment:15 in reply to: ↑ 14 Changed 10 years ago by
- Status changed from needs_work to needs_review
Replying to ncohen:
I have a question though : I build the reference to check the docstrings and noticed the file graph_colouring.pyx was not included in them : should we change it ?
An ultimate goal is to include all documentation of the Sage library in the reference manual. So, yes to your suggestion. Please open another ticket to include the file sage/graph/graph_coloring.py
in the reference manual.
comment:16 Changed 10 years ago by
- Reviewers set to Minh Van Nguyen
The patch trac_6679.patch
applies OK against Sage 4.3.alpha0. All doctests pass with the options -t -long
, apart from the following known doctest failure:
sage -t -long devel/sage/sage/interfaces/maxima.py # 1 doctests failed
The doctests also pass with the optional packages cbc-2.3.p0
and glpk-4.38.p2
, again with the above failure. In the function first_coloring
(), the function signature states that hex_colors=True
, which means that hex_colors
is True
by default. Yet, the documentation of this keyword claims otherwise. I have adjusted the documentation and value of hex_colors
accordingly. However, it's crucial that you check my changes because in the function coloring()
its default value is False
. I have attached the reviewer patch trac_6679-reviewer.patch
. Only my patch needs review. You should apply patches in this order:
trac_6679.patch
trac_6679-reviewer.patch
comment:17 Changed 10 years ago by
- Reviewers changed from Minh Van Nguyen to Karl-Dieter Crisman, Minh Van Nguyen
comment:18 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Well, graph coloring may be used to plot graphs but most of the time, its output is used to do more interesting things, so I think settng the default behaviour to returning the partition of independent sets is safe :-)
Short of this :
- I'll remember to use xrange instead of range
- I'll try not to go beyond 70 characters *even in the code*
- I'll put more spaces in my code
And I thank you very very very much for your help !!! I agreed with all of your changes while reading the patch file, you're doing a great job !!
Nathann
comment:19 Changed 10 years ago by
- Merged in set to sage-4.3.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
First patch !