Opened 8 years ago
Last modified 5 years ago
#12379 new enhancement
Graph chromatic_number - change default algorithm.
Reported by: | JoalHeagney | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.4 |
Component: | graph theory | Keywords: | graph, MILP, chromatic_number |
Cc: | Merged in: | ||
Authors: | JoalHeagney | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The following page in the documentation (and the sage docstring for this method) http://www.sagemath.org/doc/reference/sage/graphs/graph.html states chromatic_number uses the less efficient DLX algorithm by default, as opposed to the MILP algorithm.
It's my understanding that sage now includes GLPK by default.
I'd recommend that the default be changed to the more efficient algorithm="MILP".
I've already created a ticket http://trac.sagemath.org/sage_trac/ticket/12378 for the required change in documentation.
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.
Change History (7)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
A student in my class -- Andrew Johnson -- looked at doing this ticket. But he was surprised to find that your assertion that
g = graphs.CubeGraph(11) time g.chromatic_number(algorithm='DLX') Time: CPU 0.27 s, Wall: 0.27 s time g.chromatic_number(algorithm='MILP') Time: CPU 0.06 s, Wall: 0.06 s
But the next one has DLX way ahead:
g = graphs.RandomGNP(30, .4) time g.chromatic_number(algorithm='DLX') Time: CPU 1.37 s, Wall: 1.37 s time g.chromatic_number(algorithm='MILP') Time: CPU 11.29 s, Wall: 11.30 s
comment:3 Changed 8 years ago by
I just wrote this:
def use_all(f, algorithms): @parallel(len(algorithms), verbose=False) def h(alg): return f(algorithm=alg) for input, output in h(algorithms): return output, input[0][0]
which one can use like this:
set_random_seed(0) g = graphs.RandomGNP(20, .5) time use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
This way all algorithms get run, and the first to finish is used. This could be useful. Perhaps my function above could go in devel/sage-main/sage/parallel/algorithm.py and provide a way to easily implement an algorithm="parallel" option.
comment:4 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
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.