Dancing Links internal pyx code
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]]