dancing links: find all solutions in parallel #25125

seblabbe · 2018-04-09T06:31:19Z

Add all_solutions method so that one can do:

sage: S = Subsets(range(4))
sage: rows = map(list, S)
sage: dlx = dlx_solver(rows)
sage: dlx
Dancing links solver for 4 columns and 16 rows
sage: dlx.number_of_solutions()
15
sage: sorted([sorted(s) for s in dlx.all_solutions(ncpus=8)])
[[1, 2, 3, 4],
 [1, 2, 10],
 [1, 3, 9],
 [1, 4, 8],
 [1, 14],
 [2, 3, 7],
 [2, 4, 6],
 [2, 13],
 [3, 4, 5],
 [3, 12],
 [4, 11],
 [5, 10],
 [6, 9],
 [7, 8],
 [15]]

Component: combinatorics

Keywords: thursdaysbdx

Author: Sébastien Labbé

Branch/Commit: c985179

Reviewer: Julian Rüth, Vincent Delecroix, Vincent Klein

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

The text was updated successfully, but these errors were encountered:

seblabbe · 2018-04-09T06:33:33Z

Commit: c4aa595

seblabbe · 2018-04-09T06:33:33Z

Branch: u/slabbe/25125

seblabbe · 2018-04-09T06:33:33Z

New commits:

`c4aa595`	`25125: add all_solutions method to dancing links`

mantepse · 2018-04-09T09:32:50Z

comment:3

spliting -> splitting

add a test / example for parallel?

sagetrac-git · 2018-04-09T20:50:45Z

Branch pushed to git repo; I updated commit sha1. New commits:

`71b8683`	`25125: fix doc`

sagetrac-git · 2018-04-09T20:50:45Z

Changed commit from c4aa595 to 71b8683

seblabbe · 2018-04-09T20:53:52Z

comment:5

Since tests are often run in parallel, I know Volker does not like when doctests use more than one cpus. Instead I added a sentence explaining how to use ncpus argument.

re-needs_review.

saraedum · 2018-04-12T17:34:21Z

comment:6

I think you forgot to set the "Author" on this ticket.

saraedum · 2018-04-12T17:41:40Z

Reviewer: Julian Rüth

saraedum · 2018-04-12T17:41:40Z

comment:7

I think it's a bit weird that the ncpus example does not actually set ncpus>1. It's understandable from your comment on the ticket why you did that but it's not understandable from looking at the code. I think it would be nice to add a comment to the docstring.

Why do you set ncpus=1 as a default? Shouldn't the default just be None? During doctests that is going to be "2" which seems to be Ok for doctesting, see ncpus.py.

seblabbe · 2018-04-12T19:25:56Z

Author: Sébastien Labbé

seblabbe · 2018-04-12T19:32:44Z

comment:9

Replying to @seblabbe:

I know Volker does not like when doctests use more than one cpus

For reference, here is the previous discussion on this aspect:
#24424 comment:3

At #24424, in the end, I wrote ncpus=2 in the doctests.

sagetrac-git · 2018-04-12T19:48:50Z

Branch pushed to git repo; I updated commit sha1. New commits:

`3073811`	`25125: setting ncpus=None as default`

sagetrac-git · 2018-04-12T19:48:50Z

Changed commit from 71b8683 to 3073811

saraedum · 2018-04-12T19:51:02Z

comment:12

If parallelity is what people usually want in #24424 as well, then None should be the default there as well I think.

saraedum · 2018-04-12T19:52:31Z

comment:13

The docstrings do not really work anymore now. It's not explained what `None` means. Also the example about parallel computation is not really different from the "non-parallel" one that is parallel as well.

seblabbe · 2018-04-12T20:32:41Z

comment:14

Ok, thanks for your comment. I will rework on this in a few days. I need to prepare for a travel.

sagetrac-git · 2018-04-22T14:17:44Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`9448bfd`	`25125: add all_solutions method to dancing links`
`f6257b8`	`25125: fix doc`
`876bfd3`	`25125: setting ncpus=None as default`
`606c156`	`25125: improved sentences before some doctests`
`0a86ab2`	`rewriting number_of_solutions method like one_solution and all_solutions`

sagetrac-git · 2018-04-22T14:17:44Z

Changed commit from 3073811 to 0a86ab2

seblabbe · 2018-05-18T19:14:44Z

comment:33

And are you able to reproduce the problem mentionned by Volker with commit a5c4667 ?

vinklein · 2018-05-22T07:13:20Z

comment:34

Yes ! I should have mentioned that.

vinklein · 2018-05-22T11:46:46Z

comment:35

d13e0ec fix the problem.

seblabbe · 2018-05-22T11:56:32Z

comment:36

Thanks for your help testing on OSX.

Sébastien

vbraun · 2018-05-23T21:41:53Z

comment:37

sage -t --long src/sage/combinat/matrices/dancing_links.pyx
**********************************************************************
File "src/sage/combinat/matrices/dancing_links.pyx", line 683, in sage.combinat.matrices.dancing_links.dancing_linksWrapper.all_solutions
Failed example:
    [sorted(s) for s in S]
Expected:
    [[0, 1], [2, 3], [4, 5]]
Got:
    [[0, 1], [4, 5], [2, 3]]
**********************************************************************
1 item had failures:
   1 of  16 in sage.combinat.matrices.dancing_links.dancing_linksWrapper.all_solutions
    [215 tests, 1 failure, 7.16 s]

sagetrac-git · 2018-05-24T08:13:35Z

Changed commit from d13e0ec to 25da49e

sagetrac-git · 2018-05-24T08:13:35Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`9a158e6`	`25125: add all_solutions method to dancing links`
`89b5901`	`25125: fix doc`
`c54a64d`	`25125: setting ncpus=None as default`
`cf7b435`	`25125: improved sentences before some doctests`
`004126a`	`rewriting number_of_solutions method like one_solution and all_solutions`
`d18e090`	`25125: allow reinitialization of dlx solver`
`c05e73b`	`25125: reinitialize the dlx solver when needed`
`10f885d`	`25125: Calling constructor dancing_links() only in reinitialize not in __init__`
`25da49e`	`25125: sorted lists in doctests`

seblabbe · 2018-05-24T09:13:05Z

comment:40

Sorry Volker. I was sure that I put sorted everywhere needed, but I forgot one.

Rebased on 8.3.beta2.

I added a commit which added the sorted where the doctest problem occurs. I also added two other sorted elsewhere.

Needs review.

vinklein · 2018-05-29T09:24:33Z

comment:41

sage -t -a works on ubuntu and OSX ( except for ext_rep.py and external.py killed due to abort signal, which is not related to this ticket).

vinklein · 2018-05-29T09:35:27Z

comment:42

Random errors on dancing_links.pyx on OSX.

sage admin$ for i in `seq 0 50` ; do ./sage -t --long src/sage/combinat/matrices/dancing_links.pyx ; done
...
sage -t --long --warn-long 46.8 src/sage/combinat/matrices/dancing_links.pyx
    [215 tests, 5.41 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 5.5 seconds
    cpu time: 4.8 seconds
    cumulative wall time: 5.4 seconds
macbookpro-sierra-02:sage admin$ for i in `seq 0 50` ; do ./sage -t --long src/sage/combinat/matrices/dancing_links.pyx ; done
Running doctests with ID 2018-05-29-11-30-55-9317aab4.
Git branch: t/25125/25125
Using --optional=gfortran,gmpy2,mpir,python2,sage
Doctesting 1 file.
sage -t --long --warn-long 46.8 src/sage/combinat/matrices/dancing_links.pyx
**********************************************************************
File "src/sage/combinat/matrices/dancing_links.pyx", line 603, in sage.combinat.matrices.dancing_links.dancing_linksWrapper.one_solution
Failed example:
    sorted(d.one_solution())
Expected:
    [0, 1]
Got:
    [2, 3]
**********************************************************************
1 item had failures:
   1 of  17 in sage.combinat.matrices.dancing_links.dancing_linksWrapper.one_solution
    [215 tests, 1 failure, 5.46 s]
----------------------------------------------------------------------
sage -t --long --warn-long 46.8 src/sage/combinat/matrices/dancing_links.pyx  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 5.6 seconds
    cpu time: 4.9 seconds
    cumulative wall time: 5.5 seconds
Running doctests with ID 2018-05-29-11-31-04-c04446f2.
Git branch: t/25125/25125
Using --optional=gfortran,gmpy2,mpir,python2,sage
Doctesting 1 file.
sage -t --long --warn-long 46.8 src/sage/combinat/matrices/dancing_links.pyx
**********************************************************************
File "src/sage/combinat/matrices/dancing_links.pyx", line 634, in sage.combinat.matrices.dancing_links.dancing_linksWrapper.one_solution
Failed example:
    sorted(dlx.one_solution())
Expected:
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Got:
    [2, 3, 4, 5, 6, 7, 9, 10, 11, 18]
**********************************************************************
1 item had failures:
   1 of  17 in sage.combinat.matrices.dancing_links.dancing_linksWrapper.one_solution
    [215 tests, 1 failure, 5.42 s]
----------------------------------------------------------------------
sage -t --long --warn-long 46.8 src/sage/combinat/matrices/dancing_links.pyx  # 1 doctest failed

sagetrac-git · 2018-05-30T19:44:40Z

Changed commit from 25da49e to c985179

sagetrac-git · 2018-05-30T19:44:40Z

Branch pushed to git repo; I updated commit sha1. New commits:

`c985179`	`25125: sorting every list even those of size one in doctests`

seblabbe · 2018-05-30T19:54:53Z

comment:45

Thanks for your carefull review Vincent K. We avoided a nuisance to Volker.

The failures you found come from the fact that we change the ncpus=1 to ncpus=None in the one_solution method which made deterministic doctests become not deterministic. If the doctest is run with more than one cpu, than the first solution found depend on the speed of the computation made on each cpus.

I made the doctests for one_solution independent of the first solution found.

I also added a bunch of sorted (even for list of size one!) to prevents other similar problem.

Hopefully, these were the last non deterministic doctests to be fixed.

Needs review.

vinklein · 2018-06-01T14:02:33Z

comment:46

All tests passed (with several iteration of sage -t ...dancing_links.pyx) both on unbuntu and osx.

vbraun · 2018-06-02T16:11:47Z

Changed branch from u/slabbe/25125 to c985179

seblabbe added this to the sage-8.2 milestone Apr 9, 2018

seblabbe added c: combinatorics labels Apr 9, 2018

seblabbe added the s: needs review label Apr 9, 2018

saraedum added s: needs info and removed s: needs review labels Apr 12, 2018

seblabbe added s: needs review and removed s: needs info labels Apr 12, 2018

saraedum added s: needs work and removed s: needs review labels Apr 12, 2018

vinklein mannequin added s: positive review and removed s: needs review labels May 22, 2018

vbraun added s: needs work and removed s: positive review labels May 23, 2018

seblabbe added s: needs review and removed s: needs work labels May 24, 2018

vinklein mannequin added s: needs work and removed s: needs review labels May 29, 2018

seblabbe added s: needs review and removed s: needs work labels May 30, 2018

vinklein mannequin added s: positive review and removed s: needs review labels Jun 1, 2018

vbraun removed the s: positive review label Jun 2, 2018

vbraun closed this as completed in bf2f2b9 Jun 2, 2018

seblabbe mentioned this issue May 1, 2018

GeneralDiscreteDistribution broken when entries >= 2^1024 #24416

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

dancing links: find all solutions in parallel #25125

dancing links: find all solutions in parallel #25125

seblabbe commented Apr 9, 2018

seblabbe commented Apr 9, 2018

seblabbe commented Apr 9, 2018

seblabbe commented Apr 9, 2018

mantepse commented Apr 9, 2018

sagetrac-git mannequin commented Apr 9, 2018

sagetrac-git mannequin commented Apr 9, 2018

seblabbe commented Apr 9, 2018

saraedum commented Apr 12, 2018

saraedum commented Apr 12, 2018

saraedum commented Apr 12, 2018

seblabbe commented Apr 12, 2018

seblabbe commented Apr 12, 2018

sagetrac-git mannequin commented Apr 12, 2018

sagetrac-git mannequin commented Apr 12, 2018

saraedum commented Apr 12, 2018

saraedum commented Apr 12, 2018

seblabbe commented Apr 12, 2018

sagetrac-git mannequin commented Apr 22, 2018

sagetrac-git mannequin commented Apr 22, 2018

seblabbe commented May 18, 2018

vinklein mannequin commented May 22, 2018

vinklein mannequin commented May 22, 2018

seblabbe commented May 22, 2018

vbraun commented May 23, 2018

sagetrac-git mannequin commented May 24, 2018

sagetrac-git mannequin commented May 24, 2018

seblabbe commented May 24, 2018

vinklein mannequin commented May 29, 2018

vinklein mannequin commented May 29, 2018

sagetrac-git mannequin commented May 30, 2018

sagetrac-git mannequin commented May 30, 2018

seblabbe commented May 30, 2018

vinklein mannequin commented Jun 1, 2018

vbraun commented Jun 2, 2018

dancing links: find all solutions in parallel #25125

dancing links: find all solutions in parallel #25125

Comments

seblabbe commented Apr 9, 2018

seblabbe commented Apr 9, 2018

seblabbe commented Apr 9, 2018

seblabbe commented Apr 9, 2018

mantepse commented Apr 9, 2018

sagetrac-git mannequin commented Apr 9, 2018

sagetrac-git mannequin commented Apr 9, 2018

seblabbe commented Apr 9, 2018

saraedum commented Apr 12, 2018

saraedum commented Apr 12, 2018

saraedum commented Apr 12, 2018

seblabbe commented Apr 12, 2018

seblabbe commented Apr 12, 2018

sagetrac-git mannequin commented Apr 12, 2018

sagetrac-git mannequin commented Apr 12, 2018

saraedum commented Apr 12, 2018

saraedum commented Apr 12, 2018

The docstrings do not really work anymore now. It's not explained what None means. Also the example about parallel computation is not really different from the "non-parallel" one that is parallel as well.

seblabbe commented Apr 12, 2018

sagetrac-git mannequin commented Apr 22, 2018

sagetrac-git mannequin commented Apr 22, 2018

seblabbe commented May 18, 2018

vinklein mannequin commented May 22, 2018

vinklein mannequin commented May 22, 2018

seblabbe commented May 22, 2018

vbraun commented May 23, 2018

sagetrac-git mannequin commented May 24, 2018

sagetrac-git mannequin commented May 24, 2018

seblabbe commented May 24, 2018

vinklein mannequin commented May 29, 2018

vinklein mannequin commented May 29, 2018

sagetrac-git mannequin commented May 30, 2018

sagetrac-git mannequin commented May 30, 2018

seblabbe commented May 30, 2018

vinklein mannequin commented Jun 1, 2018

vbraun commented Jun 2, 2018

The docstrings do not really work anymore now. It's not explained what `None` means. Also the example about parallel computation is not really different from the "non-parallel" one that is parallel as well.