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:

Status badges

Description (last modified by dcoudert)

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 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:

e699e07trac #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:

1475514trac #12379: merged with 9.6
e05de25trac #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.