Opened 10 years ago
Last modified 8 days ago
#12379 needs_review enhancement
add parallel algorithm to Graph chromatic_number
Reported by:  JoalHeagney  Owned by:  jason, ncohen, rlm 

Priority:  minor  Milestone:  sage9.7 
Component:  graph theory  Keywords:  graph, MILP, chromatic_number 
Cc:  Merged in:  
Authors:  Joal Heagney, David Coudert  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  public/graphs/12379_parallel (Commits, GitHub, GitLab)  Commit:  e05de25cfb8d09ca62382984b84b5b595f23358f 
Dependencies:  Stopgaps: 
Description (last modified by )
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
Change History (13)
comment:1 Changed 10 years ago by
 Description modified (diff)
comment:2 Changed 10 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 10 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/sagemain/sage/parallel/algorithm.py and provide a way to easily implement an algorithm="parallel" option.
comment:4 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:5 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:8 Changed 4 weeks ago by
 Branch set to public/graphs/12379_parallel
 Commit set to e699e07718b87432315cd4b373afd2795e095e40
 Description modified (diff)
 Milestone changed from sage6.4 to sage9.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 warnlong 290.4 randomseed=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
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
 Description modified (diff)
comment:11 Changed 8 days ago by
 Commit changed from e699e07718b87432315cd4b373afd2795e095e40 to e05de25cfb8d09ca62382984b84b5b595f23358f
comment:12 Changed 8 days ago by
the preview doctest was subject to errors. This is more robust now.
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 alreadywritten MILP alternatives.