org.apache.hadoop.examples.dancing

类 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.

嵌套类概要

嵌套类

限定符和类型	类和说明
static interface	DancingLinks.SolutionAcceptor<ColumnName> Applications should implement this to receive the solutions to their problems.

构造器概要

构造器

构造器和说明
DancingLinks()

方法概要

方法

限定符和类型	方法和说明
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.

从类继承的方法 java.lang.Object

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

构造器详细资料

DancingLinks

public DancingLinks()

方法详细资料

addColumn

public void addColumn(ColumnName name,
             boolean primary)

Add a column to the table

参数:

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

参数:

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

getNumberColumns

public int getNumberColumns()

Get the number of columns.

返回:

the number of columns

getColumnName

public String getColumnName(int index)

Get the name of a given column as a string

参数:

index - the index of the column

返回:

a string representation of the name

addRow

public void addRow(boolean[] values)

Add a row to the table.

参数:

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.

参数:

depth - the length of the prefixes to generate

返回:

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.

参数:

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

output - the output for each solution

返回:

the number of solutions

solve

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

Solve a complete problem

参数:

output - the acceptor to receive answers

返回:

the number of solutions