org.apache.hadoop.examples.dancing
Class DancingLinks<ColumnName>

java.lang.Object
  org.apache.hadoop.examples.dancing.DancingLinks<ColumnName>

public class DancingLinks<ColumnName>
extends Object

A generic solver for tile laying problems using Knuth's dancing link algorithm. It provides a very fast backtracking data structure for problems that can expressed as a sparse boolean matrix where the goal is to select a subset of the rows such that each column has exactly 1 true in it. The application gives each column a name and each row is named after the set of columns that it has as true. Solutions are passed back by giving the selected rows' names. The type parameter ColumnName is the class of application's column names.

Nested Class Summary

static interface

DancingLinks.SolutionAcceptor<ColumnName> Applications should implement this to receive the solutions to their problems.

Constructor Summary

DancingLinks()

Method Summary

void	addColumn(ColumnName name) Add a column to the table
void	addColumn(ColumnName name, boolean primary) Add a column to the table
void	addRow(boolean[] values) Add a row to the table.
String	getColumnName(int index) Get the name of a given column as a string
int	getNumberColumns() Get the number of columns.
int	solve(DancingLinks.SolutionAcceptor<ColumnName> output) Solve a complete problem
int	solve(int[] prefix, DancingLinks.SolutionAcceptor<ColumnName> output) Given a prefix, find solutions under it.
List<int[]>	split(int depth) Generate a list of row choices to cover the first moves.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DancingLinks

public DancingLinks()

Method Detail

addColumn

public void addColumn(ColumnName name,
                      boolean primary)

Add a column to the table

Parameters:

name - The name of the column, which will be returned as part of solutions

primary - Is the column required for a solution?

addColumn

public void addColumn(ColumnName name)

Add a column to the table

Parameters:

name - The name of the column, which will be included in the solution

getNumberColumns

public int getNumberColumns()

Get the number of columns.

Returns:

the number of columns

getColumnName

public String getColumnName(int index)

Get the name of a given column as a string

Parameters:

index - the index of the column

Returns:

a string representation of the name

addRow

public void addRow(boolean[] values)

Add a row to the table.

Parameters:

values - the columns that are satisfied by this row

split

public List<int[]> split(int depth)

Generate a list of row choices to cover the first moves.

Parameters:

depth - the length of the prefixes to generate

Returns:

a list of integer arrays that list the rows to pick in order

solve

public int solve(int[] prefix,
                 DancingLinks.SolutionAcceptor<ColumnName> output)

Given a prefix, find solutions under it.

Parameters:

prefix - a list of row choices that control which part of the search tree to explore

output - the output for each solution

Returns:

the number of solutions

solve

public int solve(DancingLinks.SolutionAcceptor<ColumnName> output)

Solve a complete problem

Parameters:

output - the acceptor to receive answers

Returns:

the number of solutions