Opened 3 years ago
Closed 3 years ago
#22564 closed enhancement (fixed)
Chromatic index
Reported by:  pelegm  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  graph theory  Keywords:  chromatic_index, graph_coloring 
Cc:  pelegm, kdilks, chapoton  Merged in:  
Authors:  David Coudert  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  9ffdfa8 (Commits)  Commit:  9ffdfa80c98478760b37ec89fc3e4038d2833013 
Dependencies:  Stopgaps: 
Description
We probably want to have .chromatic_index
as a graph method.
We already have .fractional_chromatic_index
as a graph method (see #10044), and .chromatic_number
as a graph method. It only makes sense to have .chromatic_index
as a graph method as well, instead of doing something like
graph_coloring.edge_coloring(g, value_only=True)
Change History (25)
comment:1 Changed 3 years ago by
comment:2 Changed 3 years ago by
I think you are confusing the chromatic number of a graph (minimum number of colours in a proper vertex colouring of the graph) and the chromatic index of a graph (minimum number of colours in a proper edge colouring of the graph).
The chromatic index is sometimes called the edge chromatic number.
comment:3 Changed 3 years ago by
You are right.
comment:4 Changed 3 years ago by
 Branch set to u/dcoudert/22564
 Cc pelegm added
 Commit set to 8ed2ebd4ba85fb4e71c79f81759b2bf212d49d13
 Milestone changed from sage7.6 to sage8.0
 Status changed from new to needs_review
I added method chromatic_index
to graph, and I have also improve the edge_coloring
method to handle non connected graphs.
New commits:
81a9587  trac #22564: add method chromatic index to Graph

e1a7a80  trac #22564: clean graph_coloring.edge_coloring

8ed2ebd  trac #22564: improve edge_coloring for non connected graphs

comment:5 Changed 3 years ago by
Trying to review your branch, I checked out into your branch, but then trying to run sage I get:
Error: You must set either the SAGE_LOCAL or SAGE_SCRIPTS_DIR environment variable to run this Error setting environment variables by sourcing '/home/peleg/sage/src/bin/sageenv'; possibly contact sagedevel (see http://groups.google.com/group/sagedevel).
Any idea what might cause this?
comment:6 Changed 3 years ago by
No, unfortunately :(
on my computer, these variables are not set. You should may be post on sagedevel.
comment:7 Changed 3 years ago by
 Commit changed from 8ed2ebd4ba85fb4e71c79f81759b2bf212d49d13 to ee9ed4a578bf6e29d6769d24882b184fd89ab665
comment:8 Changed 3 years ago by
 Cc kdilks added
comment:9 Changed 3 years ago by
any help to review this patch is more than welcome ;)
comment:10 Changed 3 years ago by
I've looked over things a little bit, still need to look over the code more carefully and try to break things.
In terms of the docstrings, for chromatic_index()
:
 I think that mentioning that the method is a frontend and the
See also:
should be placed afterINPUT:
, but beforeEXAMPLES:
.
 I don't think there's much of a point to doing
n=randint(3,6)
, because I believe Sage always uses the same initial seed for random number generation in tests. Which means it won't succeed in finding errors like...
 Chromatic index of a complete graph K_n is equal to n if n is odd, and n1 if n is even. It is not always equal to n as stated. Presumably doctests are always "randomly" picking n to be 3 or 5, since they never pick this up.
 I think instead of having two examples with the path graph, it might be better to do one example with the path graph, and one or two examples with more 'exotic' graphs (Maybe petersen graph and some graph that isn't regular?).
For edge_coloring()
:
 There needs to be some examples in the documentation showing/testing what happens when
value_only=False
and an edge partition is returned.
 It's also not entirely clear from the documentation what is supposed to happen when
hex_colors=False
.
comment:11 Changed 3 years ago by
Just realized that the edge_coloring()
was already in Sage and not really part of this ticket...so I guess only do that if you're feeling particularly expeditious :) .
comment:12 Changed 3 years ago by
 Commit changed from ee9ed4a578bf6e29d6769d24882b184fd89ab665 to f9c0c00fd88c7390a3c4cfccef689c350d7f61ad
comment:13 Changed 3 years ago by
I addressed all your comments. It's true that the edge_coloring
method was lacking of examples.
On my side it passes all tests and I can build/display properly the doc. Hope it's the same for you.
Don't forget to add your real name as a reviewer. Thanks.
comment:14 Changed 3 years ago by
 Commit changed from f9c0c00fd88c7390a3c4cfccef689c350d7f61ad to 9ffdfa80c98478760b37ec89fc3e4038d2833013
comment:15 Changed 3 years ago by
The solution of edge_coloring
depends on the ILP solver. My default solver is cplex, which is not the case of the patchbot. I'm now forcing GLPK
in the examples.
comment:16 Changed 3 years ago by
 Reviewers set to Kevin Dilks
Only last thing I see that needs to be addressed is that Patchbot is not happy with something about the .. SEE ALSO:
blocks, but I'm not sure exactly what. My best guess would be that See also:
is reserved for things that link within the software/documentation, and links to external references like Wikipedia should be in a References
section.
comment:17 Changed 3 years ago by
As far as I know, the use of the .. SEEALSO::
block is correct, so I don't understand why the patchbot is complaining :(
comment:18 Changed 3 years ago by
The patchbot plugin is likely not quite smart enough for the .. SEEALSO::
blocks (could just be a missed case in the implementation; maybe ask Frédéric). It is okay to ignore the patchbot output as it is mostly a guidepost rather than a hard rule (provided the doc builds of course).
comment:19 Changed 3 years ago by
 Cc chapoton added
comment:20 Changed 3 years ago by
Hi Frédéric,
if you have any idea what's going on here, please let us know. I tried to follow all rules for the formatting of blocks, but the patchbot is complaining. On my side, I can successfully build the documentation and it displays well.
Thanks, David.
comment:21 Changed 3 years ago by
This was an issue in patchbot 2.6.9, fixed in patchbot 2.7.0. Just forget about it, as Travis told you already.
comment:22 Changed 3 years ago by
ok, Thanks.
comment:23 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:24 Changed 3 years ago by
Thanks for the review.
comment:25 Changed 3 years ago by
 Branch changed from u/dcoudert/22564 to 9ffdfa80c98478760b37ec89fc3e4038d2833013
 Resolution set to fixed
 Status changed from positive_review to closed
graph_coloring
is in the global namespace. It should be access either asGraph
methods or using an import.G.coloring()
. We could certainly add an alias for the chromatic number, but it is essentially the same