Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#7734 closed defect (fixed)

edge_coloring loops forever when GLPK is not installed

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: rlm Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

As the title says... :-)

This patch can be qualified of "short" :p

Attachments (2)

trac_7734.patch​ (1.0 KB) - added by ncohen 10 years ago.
trac_7734-edit.patch​ (5.9 KB) - added by rlm 10 years ago.

Download all attachments as: .zip

Change History (11)

Changed 10 years ago by ncohen

comment:1 Changed 10 years ago by ncohen

  • Cc rlm added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 10 years ago by rlm

  • Status changed from needs_review to positive_review
  1. There should always be an example of the bug you are fixing in the patch, always always always. We need a mug shot, so the bug doesn't show its face again :) I added this, as well as several other tests, which have exposed other corner case bugs, such as: 
    sage: g = Graph(20)
sage: vertex_coloring(g, hex_colors=True)
{'#ff0000': 0}

I've fixed these.

  1. It seems to take some time to add constraints to the problem, which is pointless if no solver is installed. Can you add a patch that runs a trivial test before setting up the problem, to see if it is installed?

Changed 10 years ago by rlm

comment:3 Changed 10 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller

comment:4 Changed 10 years ago by rlm

  • Summary changed from edge_coloring ( and possibly vertex_coloring ) loop forever when GLPK is not installed to edge_coloring loops forever when GLPK is not installed

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

Thank you for your help !!!

Concerning your second point : do you have an example for which it takes some time ? I would also like to try to improve it a bit :-)

comment:6 in reply to: ↑ 5 Changed 10 years ago by rlm

Replying to ncohen:

Thank you for your help !!!

do you have an example for which it takes some time ? I would also like to try to improve it a bit :-) 

sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.CirculantGraph(120, [2,3,5,7])
sage: vertex_coloring(g)

It takes longer to set up the constraint than to solve the problem, on my laptop.

comment:7 Changed 10 years ago by ncohen

I just created #7740 to deal with the problem of speed. What would you advise for the detection of the solver ? At the moment, only the "solve" command requires an optional package to be installed, do you think it would be worth changing this and make the whole class depend on GLPK or CBC ?

Nathann

comment:8 Changed 10 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:9 Changed 10 years ago by mhansen

  • Milestone changed from sage-4.3.1 to sage-4.3
Note: See TracTickets for help on using tickets.