[massively positive review] Include Antti Ajanki's DLX library

[boothby]

The Dancing Links algorithm (DLX) is sweet. It solves the Exact Cover problem with the quickness.

Arguments for including Ajanki's code:

• It's the only Python implementation of DLX I've seen.
• I emailed the author, who happily added the "or later" bit after the GPL2
• With my Sage Matrix -> DLXMatrix code (plus docstrings to everything I added), the file dlx.py is only 8kB!
• It will resolve tickets graphs: calculate chromatic number #1311 and [is implemented in #1311] graphs: calculate chromatic polynomial #1313

Component: combinatorics

Issue created by migration from https://trac.sagemath.org/ticket/2271

[boothby]

Attachment: 2271_adds_DLX.hg.gz

[williamstein]

comment:2

+1 to include this in Sage.

I haven't formally refereed it.

You should just attach a single plain text patch instead of an hg bundle.

[boothby]

comment:4

Oops, I forgot to add the functions to all.py, so the tests fail. New patch up in a few.

[rlmill]

comment:5

Attachment: 2271_adds_DLX.patch.gz

This patch (although awesome) doesn't quite obey the new doctest-for-every-function rule, since the following functions do not have doctests:

1. walknodes
2. constructmatrix
3. covercolumn
4. uncovercolumn
5. dosearch
6. solve

[boothby]

Attachment: 2271_doctests.patch.gz

[boothby]

comment:7

2271_doctests.patch implements world peace, washes your dishes, and makes coffee before your alarm goes off in the morning. It's truly amazing. Also, it contains doctests for everything in sight, reworks the DLXMatrix class to be a real python generator class, and implements an iterative formulation of DLX.

In the creation of these doctests, I have discovered a wondrous resolution of P vs. NP, but the proof was too long to justify appending to the patch.

[rlmill]

comment:8

As well as a round of applause.

[sagetrac-mabshoff]

comment:9

Replying to @boothby:

2271_doctests.patch implements world peace, washes your dishes, and makes coffee before your alarm goes off in the morning. It's truly amazing. Also, it contains doctests for everything in sight, reworks the DLXMatrix class to be a real python generator class, and implements an iterative formulation of DLX.

In the creation of these doctests, I have discovered a wondrous resolution of P vs. NP, but the proof was too long to justify appending to the patch.

I guess you should have written it in the margins :)

Cheers,

Michael

[sagetrac-mabshoff]

comment:10

Merged 2271_adds_DLX.patch and 2271_doctests.patch in Sage 2.10.3.alpha0 - w00t