Opened 3 years ago

Closed 2 years ago

#22564 closed enhancement (fixed)

Chromatic index

Reported by: pelegm Owned by:
Priority: major Milestone: sage-8.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 dcoudert

  • I don't understand why graph_coloring is in the global namespace. It should be access either as Graph methods or using an import.
  • we already have G.coloring(). We could certainly add an alias for the chromatic number, but it is essentially the same
  • observe that the chromatic index is usually for coloring vertices, not edges as in your example.

comment:2 Changed 3 years ago by pelegm

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 dcoudert

You are right.

comment:4 Changed 3 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to u/dcoudert/22564
  • Cc pelegm added
  • Commit set to 8ed2ebd4ba85fb4e71c79f81759b2bf212d49d13
  • Milestone changed from sage-7.6 to sage-8.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:

81a9587trac #22564: add method chromatic index to Graph
e1a7a80trac #22564: clean graph_coloring.edge_coloring
8ed2ebdtrac #22564: improve edge_coloring for non connected graphs

comment:5 Changed 3 years ago by pelegm

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/sage-env';
possibly contact sage-devel (see http://groups.google.com/group/sage-devel).

Any idea what might cause this?

Last edited 3 years ago by pelegm (previous) (diff)

comment:6 Changed 3 years ago by dcoudert

No, unfortunately :(

on my computer, these variables are not set. You should may be post on sage-devel.

comment:7 Changed 3 years ago by git

  • Commit changed from 8ed2ebd4ba85fb4e71c79f81759b2bf212d49d13 to ee9ed4a578bf6e29d6769d24882b184fd89ab665

Branch pushed to git repo; I updated commit sha1. New commits:

107e6f5trac #22564: Merged with 8.0.beta9
ee9ed4atrac #22564: small cleaning

comment:8 Changed 3 years ago by kdilks

  • Cc kdilks added

comment:9 Changed 2 years ago by dcoudert

any help to review this patch is more than welcome ;)

comment:10 Changed 2 years ago by kdilks

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 front-end and the See also: should be placed after INPUT:, but before EXAMPLES:.
  • 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 n-1 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 2 years ago by kdilks

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 2 years ago by git

  • Commit changed from ee9ed4a578bf6e29d6769d24882b184fd89ab665 to f9c0c00fd88c7390a3c4cfccef689c350d7f61ad

Branch pushed to git repo; I updated commit sha1. New commits:

482e07btrac #22564: Merged with 8.0.rc1
93f9521trac #22564: reviewers comments on chromatic_index
f9c0c00trac #22564: more examples for edge_coloring

comment:13 Changed 2 years ago by dcoudert

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.

Last edited 2 years ago by dcoudert (previous) (diff)

comment:14 Changed 2 years ago by git

  • Commit changed from f9c0c00fd88c7390a3c4cfccef689c350d7f61ad to 9ffdfa80c98478760b37ec89fc3e4038d2833013

Branch pushed to git repo; I updated commit sha1. New commits:

e2698f4trac #22564: Merged with 8.0.rc2
9ffdfa8trac #22564: force ILP solver

comment:15 Changed 2 years ago by dcoudert

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 2 years ago by kdilks

  • 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 2 years ago by dcoudert

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 2 years ago by tscrim

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 2 years ago by kdilks

  • Cc chapoton added

comment:20 Changed 2 years ago by dcoudert

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 2 years ago by chapoton

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 2 years ago by dcoudert

ok, Thanks.

comment:23 Changed 2 years ago by kdilks

  • Status changed from needs_review to positive_review

comment:24 Changed 2 years ago by dcoudert

Thanks for the review.

comment:25 Changed 2 years ago by vbraun

  • Branch changed from u/dcoudert/22564 to 9ffdfa80c98478760b37ec89fc3e4038d2833013
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.