Dancing Links internal pyx code¶
-
class
sage.combinat.matrices.dancing_links.
dancing_linksWrapper
¶ Bases:
object
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.
- TESTS:
- sage: rows = [[0,1,2], [1, 2]] sage: x = make_dlxwrapper(dumps(rows)) sage: loads(x.__reduce__()[1][0]) [[0, 1, 2], [1, 2]]
-
add_rows
(rows)¶ Initialize our instance of dancing_links with the given rows. This is for internal use by dlx_solver.
This doctest tests add_rows vicariously!
- TESTS:
- 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 ticket #13864 prior to the fix from trac ticket #13822:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: x = dlx_solver([]) # indirect doctest sage: x.get_solution() []
-
dumps
()¶ - TESTS:
- sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2]] sage: X = dlx_solver(rows) sage: X == loads(dumps(X)) 1 sage: rows += [[2]] sage: Y = dlx_solver(rows) sage: Y == loads(dumps(X)) 0
-
get_solution
()¶ After calling search(), we can extract a solution from the instance variable self.x.solution, a C++ vector<int> listing the rows that make up the current solution.
- TESTS:
- 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 sage: print x.get_solution() [3, 0]
-
search
()¶ - TESTS:
- 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 sage: print x.get_solution() [3, 0]
-
sage.combinat.matrices.dancing_links.
dlx_solver
(rows)¶ Internal-use wrapper for the dancing links C++ code.
- 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: print x.search() 1 sage: print x.get_solution() [3, 0] sage: print x.search() 1 sage: print x.get_solution() [3, 1, 2] sage: print x.search() 0
-
sage.combinat.matrices.dancing_links.
make_dlxwrapper
(s)¶ Create a dlx wrapper from a Python string s. This is used in unpickling. We expect s to be dumps(rows) where rows is the list of rows used to instantiate the object.
- TESTS:
- sage: rows = [[0,1,2]] sage: x = make_dlxwrapper(dumps(rows)) sage: print x.__str__() [[0, 1, 2]]