add parallel algorithm to Graph chromatic_number

[JoalHeagney]

The following page in the documentation (and the sage docstring for this method) ​https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph.html states chromatic_number uses the less efficient DLX algorithm by default, as opposed to the MILP algorithm that is sometimes more efficient.

Here, we add the 'parallel' algorithm that executes all algorithms in parallel and returns the answer as soon as one of the algorithm terminates.

---

Related ticket: #12378

[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.

[dcoudert]

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:

​e699e07

trac #12379: add parallel algorithm

[dcoudert]

To see that there is no clear winner between DLX and MILP (with cplex as default solver):

sage: from collections import Counter
sage: count = Counter()
sage: 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]
sage: for i in range(100):
....:     g = graphs.RandomGNP(20, .5)
....:     c, algo = use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
....:     count[algo] += 1
sage: count
Counter({'DLX': 79, 'MILP': 21})
sage: count = Counter()
sage: for i in range(100):
....:     g = graphs.RandomGNP(30, .4)
....:     c, algo = use_all(g.chromatic_number, ['DLX', 'MILP', 'CP'])
....:     count[algo] += 1
sage: count
Counter({'MILP': 74, 'DLX': 26})

[git]

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

​1475514	trac #12379: merged with 9.6
​e05de25	trac #12379: safer doctest on random graphs

[dcoudert]

the preview doctest was subject to errors. This is more robust now.

[dcoudert]

The random doctest errors reported by the patchbot are independent from this ticket and tracked in #32773 and #33880.