Navigation

  • index
  • modules |
  • next |
  • previous |
  • Sage 9.5 Reference Manual: Combinatorics »
  • Comprehensive Module List »
  • Dancing Links internal pyx code

Dancing Links internal pyx code¶

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
Dancing links solver for 6 columns and 6 rows

The number of solutions:

sage: x.number_of_solutions()
3

Iterate over the solutions:

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:

sage: sorted(x.one_solution(ncpus=2)) # random
[0, 1]

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: sorted(map(sorted, x_using_row_2.solutions_iterator()))
[[2, 3]]

The two basic methods that are wrapped in this class are search which returns 1 if a solution is found or 0 otherwise and get_solution which return the current solution:

sage: x = dlx_solver(rows)
sage: x.search()
1
sage: x.get_solution()
[0, 1]
sage: x.search()
1
sage: x.get_solution()
[2, 3]
sage: x.search()
1
sage: x.get_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]
class sage.combinat.matrices.dancing_links.dancing_linksWrapper¶

Bases: object

A simple class that implements dancing links.

The main methods to list the solutions are search() and get_solution(). You can also use number_of_solutions() to count them.

This class simply wraps a C++ implementation of Carlo Hamalainen.

all_solutions(ncpus=None, column=None)¶

Return all solutions found after splitting the problem to allow parallel computation.

INPUT:

  • ncpus – integer (default: None), maximal number of subprocesses to use at the same time. If None, it detects the number of effective CPUs in the system using sage.parallel.ncpus.ncpus().

  • column – integer (default: None), the column used to split the problem, if None a random column is chosen

OUTPUT:

list of solutions

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: S = d.all_solutions()
sage: sorted(sorted(s) for s in S)
[[0, 1], [2, 3], [4, 5]]

The number of CPUs can be specified as input:

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=2))
[[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]]

If ncpus=1, the computation is not done in parallel:

sage: sorted(sorted(s) for s in dlx.all_solutions(ncpus=1))
[[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]]
get_solution()¶

Return the current solution.

After a new solution is found using the method search() this method return the rows that make up the current solution.

ncols()¶

Return the number of columns.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [1,2], [0], [3,4,5]]
sage: dlx = dlx_solver(rows)
sage: dlx.ncols()
6
nrows()¶

Return the number of rows.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [1,2], [0], [3,4,5]]
sage: dlx = dlx_solver(rows)
sage: dlx.nrows()
4
number_of_solutions(ncpus=None, column=None)¶

Return the number of distinct solutions.

INPUT:

  • ncpus – integer (default: None), maximal number of subprocesses to use at the same time. If \(ncpus>1\) the dancing links problem is split into independent subproblems to allow parallel computation. If None, it detects the number of effective CPUs in the system using sage.parallel.ncpus.ncpus().

  • column – integer (default: None), the column used to split the problem, if None a random column is chosen (this argument is ignored if ncpus is 1)

OUTPUT:

integer

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.number_of_solutions()
2

The number of CPUs can be specified as input:

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.number_of_solutions(ncpus=2, column=3)
3
sage: S = Subsets(range(5))
sage: rows = map(list, S)
sage: d = dlx_solver(rows)
sage: d.number_of_solutions()
52
one_solution(ncpus=None, column=None)¶

Return the first solution found.

This method allows parallel computations which might be useful for some kind of problems when it is very hard just to find one solution.

INPUT:

  • ncpus – integer (default: None), maximal number of subprocesses to use at the same time. If None, it detects the number of effective CPUs in the system using sage.parallel.ncpus.ncpus(). If ncpus=1, the first solution is searched serially.

  • column – integer (default: None), the column used to split the problem (see restrict()). If None, a random column is chosen. This argument is ignored if ncpus=1.

OUTPUT:

list of rows or None if no solution is found

Note

For some case, increasing the number of cpus makes it faster. For other instances, ncpus=1 is faster. It all depends on problem which is considered.

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: solutions = [[0,1], [2,3], [4,5]]
sage: sorted(d.one_solution()) in solutions
True

The number of CPUs can be specified as input:

sage: sorted(d.one_solution(ncpus=2)) in solutions
True

The column used to split the problem for parallel computations can be given:

sage: sorted(d.one_solution(ncpus=2, column=4)) in solutions
True

When no solution is found:

sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]]
sage: d = dlx_solver(rows)
sage: d.one_solution() is None
True
one_solution_using_milp_solver(solver=None, integrality_tolerance=0.001)¶

Return a solution found using a MILP solver.

INPUT:

  • solver – string or None (default: None), possible values include 'GLPK', 'GLPK/exact', 'Coin', 'CPLEX', 'Gurobi', 'CVXOPT', 'PPL', 'InteractiveLP'.

OUTPUT:

list of rows or None if no solution is found

Note

When comparing the time taken by method \(one_solution\), have in mind that \(one_solution_using_milp_solver\) first creates (and caches) the MILP solver instance from the dancing links solver. This copy of data may take many seconds depending on the size of the problem.

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: solutions = [[0,1], [2,3], [4,5]]
sage: d.one_solution_using_milp_solver() in solutions
True

Using optional solvers:

sage: s = d.one_solution_using_milp_solver('gurobi') # optional - gurobi sage_numerical_backends_gurobi
sage: s in solutions                                 # optional - gurobi sage_numerical_backends_gurobi
True

When no solution is found:

sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]]
sage: d = dlx_solver(rows)
sage: d.one_solution_using_milp_solver() is None
True
one_solution_using_sat_solver(solver=None)¶

Return a solution found using a SAT solver.

INPUT:

  • solver – string or None (default: None), possible values include 'picosat', 'cryptominisat', 'LP', 'glucose', 'glucose-syrup'.

OUTPUT:

list of rows or None if no solution is found

Note

When comparing the time taken by method \(one_solution\), have in mind that \(one_solution_using_sat_solver\) first creates the SAT solver instance from the dancing links solver. This copy of data may take many seconds depending on the size of the problem.

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: solutions = [[0,1], [2,3], [4,5]]
sage: d.one_solution_using_sat_solver() in solutions
True

Using optional solvers:

sage: s = d.one_solution_using_sat_solver('glucose') # optional - glucose
sage: s in solutions                                 # optional - glucose
True

When no solution is found:

sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]]
sage: d = dlx_solver(rows)
sage: d.one_solution_using_sat_solver() is None
True
reinitialize()¶

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
restrict(indices)¶

Return a dancing links solver solving the subcase which uses some given rows.

For every row that is wanted in the solution, we add a new column to the row to make sure it is in the solution.

INPUT:

  • indices – list, row indices to be found in the solution

OUTPUT:

dancing links 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: d
Dancing links solver for 6 columns and 6 rows
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 problem are:

sage: d_using_0 = d.restrict([0])
sage: d_using_0
Dancing links solver for 7 columns and 6 rows
sage: d_using_0.rows()
[[0, 1, 2, 6], [3, 4, 5], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]

After restriction the subproblem has one more columns and the same number of rows as the original one:

sage: d.restrict([1]).rows()
[[0, 1, 2], [3, 4, 5, 6], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]
sage: d.restrict([2]).rows()
[[0, 1, 2], [3, 4, 5], [0, 1, 6], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]

This method allows to find solutions where the 0th row is part of a solution:

sage: sorted(map(sorted, d.restrict([0]).solutions_iterator()))
[[0, 1]]

Some other examples:

sage: sorted(map(sorted, d.restrict([1]).solutions_iterator()))
[[0, 1]]
sage: sorted(map(sorted, d.restrict([2]).solutions_iterator()))
[[2, 3]]
sage: sorted(map(sorted, d.restrict([3]).solutions_iterator()))
[[2, 3]]

Here there are no solution using both 0th and 3rd row:

sage: list(d.restrict([0,3]).solutions_iterator())
[]
rows()¶

Return the list of rows.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [1,2], [0]]
sage: x = dlx_solver(rows)
sage: x.rows()
[[0, 1, 2], [1, 2], [0]]
search()¶

Search for a new solution.

Return 1 if a new solution is found and 0 otherwise. To recover the solution, use the method get_solution().

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]
solutions_iterator()¶

Return an iterator of the solutions.

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: sorted(map(sorted, d.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
split(column)¶

Return a dict of independent solvers.

For each i-th row containing a 1 in the column, the dict associates the solver giving all solution using the i-th row.

This is used for parallel computations.

INPUT:

  • column – integer, the column used to split the problem into independent subproblems

OUTPUT:

dict where keys are row numbers and values are dlx solvers

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: d
Dancing links solver for 6 columns and 6 rows
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 number of rows as the original problem:

sage: D = d.split(0)
sage: D
{0: Dancing links solver for 7 columns and 6 rows,
 2: Dancing links solver for 7 columns and 6 rows,
 4: Dancing links solver for 7 columns and 6 rows}

The (disjoint) union of the solutions of the subproblems is equal to the set of solutions shown above:

sage: for x in D.values(): sorted(map(sorted, x.solutions_iterator()))
[[0, 1]]
[[2, 3]]
[[4, 5]]
to_milp(solver=None)¶

Return the mixed integer linear program (MILP) representing an equivalent problem.

See also sage.numerical.mip.MixedIntegerLinearProgram.

INPUT:

  • solver – string or None (default: None), possible values include 'GLPK', 'GLPK/exact', 'Coin', 'CPLEX', 'Gurobi', 'CVXOPT', 'PPL', 'InteractiveLP'.

OUTPUT:

  • MixedIntegerLinearProgram instance

  • MIPVariable with binary components

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [0,2], [1], [3]]
sage: d = dlx_solver(rows)
sage: p,x = d.to_milp()
sage: p
Boolean Program (no objective, 4 variables, 4 constraints)
sage: x
MIPVariable with 4 binary components

In the reduction, the boolean variable x_i is True if and only if the i-th row is in the solution:

sage: p.show()
Maximization:


Constraints:
  one 1 in 0-th column: 1.0 <= x_0 + x_1 <= 1.0
  one 1 in 1-th column: 1.0 <= x_0 + x_2 <= 1.0
  one 1 in 2-th column: 1.0 <= x_0 + x_1 <= 1.0
  one 1 in 3-th column: 1.0 <= x_3 <= 1.0
Variables:
  x_0 is a boolean variable (min=0.0, max=1.0)
  x_1 is a boolean variable (min=0.0, max=1.0)
  x_2 is a boolean variable (min=0.0, max=1.0)
  x_3 is a boolean variable (min=0.0, max=1.0)

Using some optional MILP solvers:

sage: d.to_milp('gurobi')   # optional - gurobi sage_numerical_backends_gurobi
(Boolean Program (no objective, 4 variables, 4 constraints),
 MIPVariable with 4 binary components)
to_sat_solver(solver=None)¶

Return the SAT solver solving an equivalent problem.

Note that row index \(i\) in the dancing links solver corresponds to the boolean variable index \(ì+1\) for the SAT solver to avoid the variable index \(0\).

See also sage.sat.solvers.satsolver.

INPUT:

  • solver – string or None (default: None), possible values include 'picosat', 'cryptominisat', 'LP', 'glucose', 'glucose-syrup'.

OUTPUT:

SAT solver instance

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [0,2], [1], [3]]
sage: x = dlx_solver(rows)
sage: s = x.to_sat_solver()

Using some optional SAT solvers:

sage: x.to_sat_solver('cryptominisat')          # optional - pycryptosat
CryptoMiniSat solver: 4 variables, 7 clauses.
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 was historically used in unpickling and is kept for backwards compatibility. We expect s to be dumps(rows) where rows is the list of rows used to instantiate the object.

Previous topic

Combinatorics on matrices

Next topic

Dancing links C++ wrapper

This Page

  • Show Source

Quick search

Navigation

  • index
  • modules |
  • next |
  • previous |
  • Sage 9.5 Reference Manual: Combinatorics »
  • Comprehensive Module List »
  • Dancing Links internal pyx code
© Copyright 2005--2022, The Sage Development Team. Created using Sphinx 4.4.0.