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

java.lang.Object
  extended by 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


Copyright © 2009 The Apache Software Foundation