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: | sage-9.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/sage-main/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 sage-5.11 to sage-5.12
comment:5 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.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 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
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 already-written MILP alternatives.