Opened 10 years ago

# add parallel algorithm to Graph chromatic_number

Reported by: Owned by: JoalHeagney jason, ncohen, rlm minor sage-9.7 graph theory graph, MILP, chromatic_number Joal Heagney, David Coudert N/A public/graphs/12379_parallel e05de25cfb8d09ca62382984b84b5b595f23358f

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

### comment:1 Changed 10 years ago by JoalHeagney

• Description modified (diff)

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.

### comment:2 Changed 10 years ago by 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
```

### comment:3 Changed 10 years ago by 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.

### comment:4 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:5 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:6 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:7 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:8 Changed 4 weeks ago by dcoudert

• Authors changed from JoalHeagney to Joal Heagney, David Coudert
• Branch set to public/graphs/12379_parallel
• Commit set to e699e07718b87432315cd4b373afd2795e095e40
• Description modified (diff)
• Milestone changed from sage-6.4 to sage-9.7
• Status changed from new to needs_review
• Summary changed from Graph chromatic_number - change default algorithm. to add parallel algorithm to Graph chromatic_number

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`

### comment:9 Changed 4 weeks ago by 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})
```

### comment:10 Changed 4 weeks ago by dcoudert

• Description modified (diff)

### comment:11 Changed 8 days ago by git

• Commit changed from e699e07718b87432315cd4b373afd2795e095e40 to e05de25cfb8d09ca62382984b84b5b595f23358f

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`

### comment:12 Changed 8 days ago by dcoudert

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

### comment:13 Changed 8 days ago by dcoudert

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

Note: See TracTickets for help on using tickets.