Navigation

  • index
  • modules |
  • next |
  • previous |
  • Combinatorics »
  • Comprehensive Module list »

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]]

Previous topic

Combinatorics on matrix features that are imported by default in the interpreter namespace

Next topic

Dancing links C++ wrapper

This Page

  • Show Source

Quick search

Enter search terms or a module, class or function name.

Navigation

  • index
  • modules |
  • next |
  • previous |
  • Combinatorics »
  • Comprehensive Module list »
© Copyright 2005--2016, The Sage Development Team. Created using Sphinx 1.3.1.