Graph chromatic_number - change default algorithm.

[JoalHeagney]

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.

[JoalHeagney]

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.

[was]

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

[was]

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.