Changes between Version 1 and Version 8 of Ticket #12379


Ignore:
Timestamp:
04/30/22 13:57:30 (2 months ago)
Author:
dcoudert
Comment:

Based on #comment:3, I have added algorithm 'parallel'. It's working well but when I tried to set it as default algorithm, I get the following issue. So it seems safer to let 'DLX' as default algorithm to avoid random doctest errors. 

sage -t --warn-long 290.4 --random-seed=83463765161747970581723517233090779640 src/sage/graphs/generators/smallgraphs.py
**********************************************************************
File "src/sage/graphs/generators/smallgraphs.py", line 4506, in sage.graphs.generators.smallgraphs.WatkinsSnarkGraph
Failed example:
    g.chromatic_number()
Expected:
    3
Got:
    Exception raised by child process with pid=40818:
    3

New commits:

​e699e07trac #12379: add parallel algorithm

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #12379

    • Property Status changed from new to needs_review
    • Property Authors changed from JoalHeagney to Joal Heagney, David Coudert
    • Property Summary changed from Graph chromatic_number - change default algorithm. to add parallel algorithm to Graph chromatic_number
    • Property Branch changed from to public/graphs/12379_parallel
    • Property Milestone changed from sage-5.11 to sage-9.7
    • Property Commit changed from to e699e07718b87432315cd4b373afd2795e095e40

  • Ticket #12379 – Description

    v1 v8  
    11The following page in the documentation (and the sage docstring for this method)
    2 [http://www.sagemath.org/doc/reference/sage/graphs/graph.html]
    3 states chromatic_number uses the less efficient DLX algorithm by default, as opposed to the MILP algorithm.
     2[https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph.html]
     3states chromatic_number uses the less efficient DLX algorithm by default, as opposed to the MILP algorithm that is sometimes more efficient.
    44
    5 It's my understanding that sage now includes GLPK by default.
     5Here, we add the `'parallel'` algorithm that executed all algorithms in parallel and returns the answer as soon as one of the algorithm terminates.
    66
    7 I'd recommend that the default be changed to the more efficient algorithm="MILP".
    8 
    9 I've already created a ticket [http://trac.sagemath.org/sage_trac/ticket/12378] for the required change in documentation.
    10 
    11 Additionally, someone should probably do a code check to see if there are other methods and functions that use default algorithms that are less efficient than already-written MILP alternatives.
     7----
     8Related ticket: #12378