Opened 6 years ago
Closed 5 years ago
#22564 closed enhancement (fixed)
Chromatic index
Reported by:  Peleg Michaeli  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  graph theory  Keywords:  chromatic_index, graph_coloring 
Cc:  Peleg Michaeli, Kevin Dilks, Frédéric Chapoton  Merged in:  
Authors:  David Coudert  Reviewers:  Kevin Dilks 
Report Upstream:  N/A  Work issues:  
Branch:  9ffdfa8 (Commits, GitHub, GitLab)  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 6 years ago by
comment:2 Changed 6 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:4 Changed 6 years ago by
Authors:  → David Coudert 

Branch:  → u/dcoudert/22564 
Cc:  Peleg Michaeli added 
Commit:  → 8ed2ebd4ba85fb4e71c79f81759b2bf212d49d13 
Milestone:  sage7.6 → sage8.0 
Status:  new → 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 6 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 6 years ago by
No, unfortunately :(
on my computer, these variables are not set. You should may be post on sagedevel.
comment:7 Changed 6 years ago by
Commit:  8ed2ebd4ba85fb4e71c79f81759b2bf212d49d13 → ee9ed4a578bf6e29d6769d24882b184fd89ab665 

comment:8 Changed 6 years ago by
Cc:  Kevin Dilks added 

comment:10 Changed 5 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 5 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 5 years ago by
Commit:  ee9ed4a578bf6e29d6769d24882b184fd89ab665 → f9c0c00fd88c7390a3c4cfccef689c350d7f61ad 

comment:13 Changed 5 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 5 years ago by
Commit:  f9c0c00fd88c7390a3c4cfccef689c350d7f61ad → 9ffdfa80c98478760b37ec89fc3e4038d2833013 

comment:15 Changed 5 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 5 years ago by
Reviewers:  → 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 5 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 5 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 5 years ago by
Cc:  Frédéric Chapoton added 

comment:20 Changed 5 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 5 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:23 Changed 5 years ago by
Status:  needs_review → positive_review 

comment:25 Changed 5 years ago by
Branch:  u/dcoudert/22564 → 9ffdfa80c98478760b37ec89fc3e4038d2833013 

Resolution:  → fixed 
Status:  positive_review → 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