summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRelease Manager <release@sagemath.org>2018-06-01 22:52:38 +0200
committerVolker Braun <vbraun.name@gmail.com>2018-06-02 11:01:17 +0200
commitbf2f2b9282b253777f18a5f57bd7c2ff862c3508 (patch)
treefa7b92e9566d2e48ee71a68e8977a5b765d6e0e6
parentTrac #24885: Add helper function to preload some libraries if necessary (diff)
parent25125: sorting every list even those of size one in doctests (diff)
Trac #25125: dancing links: find all solutions in parallel
Add `all_solutions` method so that one can do: {{{ #!python 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]] }}} URL: https://trac.sagemath.org/25125 Reported by: slabbe Ticket author(s): Sébastien Labbé Reviewer(s): Julian Rüth, Vincent Delecroix, Vincent Klein
-rw-r--r--src/sage/combinat/matrices/dancing_links.pyx400
-rw-r--r--src/sage/combinat/matrices/dancing_links_c.h9
2 files changed, 293 insertions, 116 deletions
diff --git a/src/sage/combinat/matrices/dancing_links.pyx b/src/sage/combinat/matrices/dancing_links.pyx
index 36fe946..3a50061 100644
--- a/src/sage/combinat/matrices/dancing_links.pyx
+++ b/src/sage/combinat/matrices/dancing_links.pyx
@@ -16,10 +16,14 @@ The number of solutions::
sage: x.number_of_solutions()
3
-We recreate the dancing links object and we find all solutions::
+Iterate over the solutions::
- sage: x = dlx_solver(rows)
- sage: sorted(x.solutions_iterator())
+ sage: sorted(map(sorted, x.solutions_iterator()))
+ [[0, 1], [2, 3], [4, 5]]
+
+All solutions (computed in parallel)::
+
+ sage: sorted(map(sorted, x.all_solutions()))
[[0, 1], [2, 3], [4, 5]]
Return the first solution found when the computation is done in parallel::
@@ -32,7 +36,7 @@ Find all solutions using some specific rows::
sage: x_using_row_2 = x.restrict([2])
sage: x_using_row_2
Dancing links solver for 7 columns and 6 rows
- sage: list(x_using_row_2.solutions_iterator())
+ sage: sorted(map(sorted, x_using_row_2.solutions_iterator()))
[[2, 3]]
The two basic methods that are wrapped in this class are ``search`` which
@@ -54,10 +58,18 @@ which return the current solution::
[4, 5]
sage: x.search()
0
+
+There is also a method ``reinitialize`` to reinitialize the algorithm::
+
+ sage: x.reinitialize()
+ sage: x.search()
+ 1
+ sage: x.get_solution()
+ [0, 1]
"""
#*****************************************************************************
# Copyright (C) 2008 Carlo Hamalainen <carlo.hamalainen@gmail.com>
-# Copyright (C) 2015-2017 Sébastien Labbé <slabqc@gmail.com>
+# Copyright (C) 2015-2018 Sébastien Labbé <slabqc@gmail.com>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -73,9 +85,11 @@ from cysignals.signals cimport sig_on, sig_off
cdef extern from "dancing_links_c.h":
cdef cppclass dancing_links:
+ dancing_links()
vector[int] solution
int number_of_columns()
void add_rows(vector[vector[int]] rows)
+ int search_is_started()
int search()
@@ -96,11 +110,24 @@ cdef class dancing_linksWrapper:
"""
Initialize our wrapper (self._x) as an actual C++ object.
- We must pass a list of rows at start up. There are no methods
- for resetting the list of rows, so this class acts as a one-time
- executor of the C++ code.
+ We must pass a list of rows at start up.
- TESTS::
+ EXAMPLES::
+
+ sage: from sage.combinat.matrices.dancing_links import dlx_solver
+ sage: rows = [[0,1,2]]
+ sage: rows+= [[0,2]]
+ sage: rows+= [[1]]
+ sage: rows+= [[3]]
+ sage: x = dlx_solver(rows)
+ sage: x
+ Dancing links solver for 4 columns and 4 rows
+ sage: x.search()
+ 1
+ sage: x.get_solution()
+ [3, 0]
+
+ ::
sage: rows = [[0,1,2], [1, 2]]
sage: from sage.combinat.matrices.dancing_links import dlx_solver
@@ -109,8 +136,104 @@ cdef class dancing_linksWrapper:
Dancing links solver for 3 columns and 2 rows
sage: type(x)
<... 'sage.combinat.matrices.dancing_links.dancing_linksWrapper'>
+
+ TESTS:
+
+ The following example would crash in Sage's debug version
+ from :trac:`13864` prior to the fix from :trac:`13882`::
+
+ sage: from sage.combinat.matrices.dancing_links import dlx_solver
+ sage: x = dlx_solver([])
+ sage: x.get_solution()
+ []
+
"""
- self._init_rows(rows)
+ self._rows = [row for row in rows]
+ self._initialize()
+
+ def _initialize(self):
+ r"""
+ Initialization of the search algorithm
+
+ This adds the rows to the instance of dancing_links. This method is
+ used by `__init__` and `reinitialize` methods and should not be
+ used directly.
+
+ EXAMPLES::
+
+ sage: from sage.combinat.matrices.dancing_links import dlx_solver
+ sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
+ sage: x = dlx_solver(rows) # indirect doctest
+ sage: x.get_solution() if x.search() else None
+ [0, 1]
+ sage: x.get_solution() if x.search() else None
+ [2, 3]
+
+ Reinitialization of the algorithm::
+
+ sage: x.reinitialize() # indirect doctest
+ sage: x.get_solution() if x.search() else None
+ [0, 1]
+
+ """
+ cdef vector[int] v
+ cdef vector[vector[int]] vv
+
+ for row in self._rows:
+ v.clear()
+ for x in row:
+ v.push_back(x)
+ vv.push_back(v)
+
+ sig_on()
+ self._x.add_rows(vv)
+ sig_off()
+
+ def reinitialize(self):
+ r"""
+ Reinitialization of the search algorithm
+
+ This recreates an empty `dancing_links` object and adds the rows to
+ the instance of dancing_links.
+
+ EXAMPLES::
+
+ sage: from sage.combinat.matrices.dancing_links import dlx_solver
+ sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
+ sage: x = dlx_solver(rows)
+ sage: x.get_solution() if x.search() else None
+ [0, 1]
+ sage: x.get_solution() if x.search() else None
+ [2, 3]
+
+ Reinitialization of the algorithm::
+
+ sage: x.reinitialize()
+ sage: x.get_solution() if x.search() else None
+ [0, 1]
+ sage: x.get_solution() if x.search() else None
+ [2, 3]
+ sage: x.get_solution() if x.search() else None
+ [4, 5]
+ sage: x.get_solution() if x.search() else None
+
+ Reinitialization works after solutions are exhausted::
+
+ sage: x.reinitialize()
+ sage: x.get_solution() if x.search() else None
+ [0, 1]
+ sage: x.get_solution() if x.search() else None
+ [2, 3]
+ sage: x.get_solution() if x.search() else None
+ [4, 5]
+ sage: x.get_solution() if x.search() else None
+
+ """
+ sig_on()
+ self._x = dancing_links()
+ sig_off()
+
+ self._initialize()
def __repr__(self):
"""
@@ -207,50 +330,6 @@ cdef class dancing_linksWrapper:
"""
return PyObject_RichCompare(left._rows, right._rows, op)
- def _init_rows(self, rows):
- """
- Initialize our instance of dancing_links with the given rows.
-
- This is for internal use by dlx_solver only.
-
- TESTS:
-
- This doctest tests ``_init_rows`` vicariously! ::
-
- sage: from sage.combinat.matrices.dancing_links import dlx_solver
- sage: rows = [[0,1,2]]
- sage: rows+= [[0,2]]
- sage: rows+= [[1]]
- sage: rows+= [[3]]
- sage: x = dlx_solver(rows)
- sage: print(x.search())
- 1
-
- The following example would crash in Sage's debug version
- from :trac:`13864` prior to the fix from :trac:`13882`::
-
- sage: from sage.combinat.matrices.dancing_links import dlx_solver
- sage: x = dlx_solver([]) # indirect doctest
- sage: x.get_solution()
- []
-
- """
- cdef vector[int] v
- cdef vector[vector[int]] vv
-
- self._rows = [row for row in rows]
-
- for row in self._rows:
- v.clear()
-
- for x in row:
- v.push_back(x)
-
- vv.push_back(v)
-
- sig_on()
- self._x.add_rows(vv)
- sig_off()
def get_solution(self):
"""
@@ -346,7 +425,7 @@ cdef class dancing_linksWrapper:
sage: d = dlx_solver(rows)
sage: d
Dancing links solver for 6 columns and 6 rows
- sage: sorted(d.solutions_iterator())
+ sage: sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
To impose that the 0th row is part of the solution, the rows of the new
@@ -369,16 +448,16 @@ cdef class dancing_linksWrapper:
This method allows to find solutions where the 0th row is part of a
solution::
- sage: map(sorted, d.restrict([0]).solutions_iterator())
+ sage: sorted(map(sorted, d.restrict([0]).solutions_iterator()))
[[0, 1]]
Some other examples::
- sage: map(sorted, d.restrict([1]).solutions_iterator())
+ sage: sorted(map(sorted, d.restrict([1]).solutions_iterator()))
[[0, 1]]
- sage: map(sorted, d.restrict([2]).solutions_iterator())
+ sage: sorted(map(sorted, d.restrict([2]).solutions_iterator()))
[[2, 3]]
- sage: map(sorted, d.restrict([3]).solutions_iterator())
+ sage: sorted(map(sorted, d.restrict([3]).solutions_iterator()))
[[2, 3]]
Here there are no solution using both 0th and 3rd row::
@@ -425,7 +504,7 @@ cdef class dancing_linksWrapper:
sage: d = dlx_solver(rows)
sage: d
Dancing links solver for 6 columns and 6 rows
- sage: sorted(d.solutions_iterator())
+ sage: sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
After the split each subproblem has one more column and the same
@@ -440,7 +519,7 @@ cdef class dancing_linksWrapper:
The (disjoint) union of the solutions of the subproblems is equal to the
set of solutions shown above::
- sage: for x in D.values(): list(x.solutions_iterator())
+ sage: for x in D.values(): sorted(map(sorted, x.solutions_iterator()))
[[0, 1]]
[[2, 3]]
[[4, 5]]
@@ -474,30 +553,30 @@ cdef class dancing_linksWrapper:
r"""
Return an iterator of the solutions.
- .. WARNING::
-
- This function can be used only once. To iterate through the
- solutions another time, one needs to recreate the dlx solver.
-
EXAMPLES::
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
- sage: list(d.solutions_iterator())
+ sage: sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
- As warned above, it can be used only once::
+ TESTS:
- sage: list(d.solutions_iterator())
- []
+ The algorithm is automatically reinitialized if needed, for example
+ when iterating the solutions a second time (:trac:`25125`)::
+
+ sage: sorted(map(sorted, d.solutions_iterator()))
+ [[0, 1], [2, 3], [4, 5]]
"""
+ if self._x.search_is_started():
+ self.reinitialize()
while self.search():
yield self.get_solution()
- def one_solution(self, ncpus=1, column=None):
+ def one_solution(self, ncpus=None, column=None):
r"""
- Return the first solution found after spliting the problem to
+ Return the first solution found after splitting the problem to
allow parallel computation.
Usefull when it is very hard just to find one solution to a given
@@ -505,8 +584,10 @@ cdef class dancing_linksWrapper:
INPUT:
- - ``ncpus`` -- integer (default: ``1``), maximal number of
- subprocesses to use at the same time