Opened 8 years ago

Last modified 5 years ago

#12379 new enhancement

Graph chromatic_number - change default algorithm.

Reported by: JoalHeagney Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-6.4
Component: graph theory Keywords: graph, MILP, chromatic_number
Cc: Merged in:
Authors: JoalHeagney Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by JoalHeagney)

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

It's my understanding that sage now includes GLPK by default.

I'd recommend that the default be changed to the more efficient algorithm="MILP".

I've already created a ticket http://trac.sagemath.org/sage_trac/ticket/12378 for the required change in documentation.

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.

Change History (7)

comment:1 Changed 8 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 8 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 8 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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.