Opened 10 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 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.

DEPENDS ON #7270 !!!!!!!!!!!!!

Attachments (5)

coloring-1.patch (14.5 KB) - added by ncohen 10 years ago.
First patch !
coloring-1.2.patch (14.5 KB) - added by ncohen 10 years ago.
First patch !
coloring-symbolic.patch (14.0 KB) - added by ncohen 10 years ago.
trac_6679.patch (26.8 KB) - added by ncohen 10 years ago.
trac_6679-reviewer.patch (35.4 KB) - added by mvngu 10 years ago.
based on trac_6679.patch

Download all attachments as: .zip

Change History (24)

Changed 10 years ago by ncohen

First patch !

Changed 10 years ago by ncohen

First patch !

comment:1 Changed 10 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 10 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 10 years ago by ncohen

  • Description modified (diff)

comment:4 Changed 10 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 10 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 10 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 10 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 10 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 10 years ago by ncohen

comment:9 Changed 10 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 10 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 10 years ago by ncohen

  • Description modified (diff)

comment:12 Changed 10 years ago by ncohen

Added round_robin, and a more efficient coloring for complete graphs

comment:13 Changed 10 years ago by mvngu

  • 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:

  1. 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 function chromatic_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.
  2. 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 doing algorithm=="CP", you should do algorithm == "CP". You can read more about Python coding conventions in PEP 8.
  3. 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.
  4. The formatting of docstring is inconsistent.

comment:14 follow-up: Changed 10 years ago by ncohen

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 ncohen

comment:15 in reply to: ↑ 14 Changed 10 years ago by mvngu

  • 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.

Changed 10 years ago by mvngu

based on trac_6679.patch

comment:16 Changed 10 years ago by mvngu

  • Authors set to Nathann Cohen
  • 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:

  1. trac_6679.patch
  2. trac_6679-reviewer.patch

comment:17 Changed 10 years ago by mvngu

  • Reviewers changed from Minh Van Nguyen to Karl-Dieter Crisman, Minh Van Nguyen

comment:18 Changed 10 years ago by ncohen

  • 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 mhansen

  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.