class Doku::DancingLinks::LinkMatrix

A LinkMatrix object is the Root object from Donald Knuth’s paper on Dancing Links. It also represents the matrix as a whole, so it has methods for building the matrix and finding exact covers. This data structure is used to efficiently implement Algorithm X, allowing us to find exact covers.

Public Class Methods

from_sets(sets, universe=[]) click to toggle source

Creates a new {LinkMatrix} to represent an {en.wikipedia.org/wiki/Exact_cover exact cover problem}.

Every set in the exact cover problem will be represented by a row in the matrix.

Every element in the universe of the exact cover problem will be represented by a column in the matrix. The universe is inferred by taking the union of all the sets in the sets parameter, but if you want to have control over the order of the columns then you can also make a universe array and pass it in to the universe parameter.

In {LinkMatrix}, every row has a row id. The row id is used to express exact covers when they are found. You can just let all the row ids be equal to the sets themselves by making the sets parameter be an Array or Set of sets, or you can specify the row ids explicitly by if you make the sets parameter be a hash that associates row ids to sets.

@param (Object) sets Either a hash associating row_ids to sets, or just

an array of sets.  A set is an Array or Set of objects in the
universe of the exact cover problem.

@param universe (Array) This parameter is optional. If provided, it

will define the order of the first columns of the link matrix.
It is OK if there are elements in the sets that are not present in
this array.

@return (LinkMatrix)

# File lib/doku/dancing_links.rb, line 355
def self.from_sets(sets, universe=[])
  matrix = new
  universe.each do |column_id|
    matrix.find_or_create_column column_id
  end

  if sets.is_a? Hash
    sets.each do |row_id, column_ids|
      matrix.add_row column_ids, row_id
    end
  else
    sets.each do |column_ids|
      matrix.add_row column_ids
    end
  end

  matrix
end
new() click to toggle source

Creates a new, empty matrix with no columns and no rows.

# File lib/doku/dancing_links.rb, line 287
def initialize
  @left = @right = self
  @columns = {}   # column_id object => Column
  @rows = {} # row_id object => Node
end

Public Instance Methods

add_row(column_ids, row_id=column_ids.dup) click to toggle source

Adds a row to the matrix. If a column_id is not recognized, it will be added to the matrix as a new column.

@param column_ids (Enumerable) The column_ids that are in this row. @param row_id (Object) The id of this row. This is used to express express exact covers.

# File lib/doku/dancing_links.rb, line 380
def add_row(column_ids, row_id=column_ids.dup)
  first_node = nil
  column_ids = column_ids.uniq if column_ids.respond_to?(:uniq)
  column_ids.each do |column_id|
    column = find_or_create_column(column_id)
    node = Node.new

    # Set the vertical links and column.
    node.column = column
    node.insert_above column

    # Set the horizontal links and row_id.
    node.row_id = row_id
    if first_node.nil?
      @rows[row_id] = first_node = node.left = node.right = node
    else
      node.insert_left first_node
    end

    column.size += 1
  end
end
column(id) click to toggle source

Retrieves a column object by its ID or returns nil if there is no column with that ID. @return (Column)

# File lib/doku/dancing_links.rb, line 317
def column(id)
  @columns[id]
end
columns() click to toggle source

Enumerable for all the {Column}s in the matrix.

# File lib/doku/dancing_links.rb, line 294
def columns
  LinkEnumerator.new :right, self
end
create_column(id) click to toggle source

Creates a new column with the specified ID and inserts it into the matrix as the right-most column. @param id (Object) Any object that uniquely identifies the column. @return (Column) Newly created column.

# File lib/doku/dancing_links.rb, line 308
def create_column(id)
  column = Column.new(id)
  column.insert_left self
  return @columns[id] = column
end
each_exact_cover() { |collect &:row_id| ... } click to toggle source

Searches for exact covers and yields them as it finds them. NOTE: This method mutates the LinkMatrix while it is running, but when it is finished the matrix will be back to its original state. @yield exact_cover @yieldparam exact_cover (Array) Array of row_ids of the rows/sets that are

in the cover.
# File lib/doku/dancing_links.rb, line 474
def each_exact_cover
  nodes = []   # List of nodes that are currently "covered"

  while true

    if empty?
      # Success.  Matrix is empty because every column is covered once.
      yield nodes.collect &:row_id
    end

    if column = choose_column
      # Cover a new column and pick the first node in it.
      column.cover
      node = column.down
    else
      # Uncover columns until we find one with a node we haven't tried.
      node = backtrack!(nodes)
      return if node.nil?  # Tried everything
    end

    # Try the node (push it and cover its columns).
    nodes.push node
    node.choose_except_self_column

  end
end
each_exact_cover_recursive(k=0, o=[]) { |collect &:row_id| ... } click to toggle source

This method is equivalent to {#each_exact_cover} but uses the algorithm described on page 5 of Donald Knuth’s paper “Dancing Links”. This method is just here for purists who want to be sure they are using Donald Knuth’s algorithm. For most users, it is recommended to use the more flexible, non-recursive function {#each_exact_cover} and the methods based on it: {#exact_covers} and {#find_exact_cover} because it can be difficult to debug programs with deep stacks. @return (Array) Array of row_ids of the rows/sets that are in the cover,

or nil if no exact cover was found.
# File lib/doku/dancing_links.rb, line 422
def each_exact_cover_recursive(k=0, o=[], &block)
  if right == self
    yield o[0...k].collect &:row_id   # Success
    return
  end

  c = smallest_column
  c.cover

  c.nodes_downward.each do |r|
    o[k] = r

    r.nodes_except_self_rightward.each do |j|
      j.column.cover
    end

    each_exact_cover_recursive(k+1, o, &block)
    
    r.nodes_except_self_leftward.each do |j|
      j.column.uncover
    end
  end

  c.uncover
  return nil
end
empty?() click to toggle source

True if there are no more columns left in the matrix (they were all covered). @return (Boolean)

# File lib/doku/dancing_links.rb, line 300
def empty?
  right == self
end
exact_covers() click to toggle source

Returns an enumerable that searches for exact covers as its elements are enumerated. NOTE: This method mutates the LinkMatrix. @return (Enumerable) Enumerable of exact covers. Each exact cover is

an array of row ids of the rows/sets that are in the cover.
# File lib/doku/dancing_links.rb, line 464
def exact_covers
  enum_for :each_exact_cover
end
find_exact_cover() click to toggle source

Searches for an exact cover. NOTE: This method mutates the LinkMatrix. @return (Array) Array of row ids of the rows/sets that are in the cover,

or nil if no exact cover was found.
# File lib/doku/dancing_links.rb, line 455
def find_exact_cover
  exact_covers.first
end
find_or_create_column(id) click to toggle source

Retrieves a column object by its ID or creates a new one if it didn’t exist already. @return (Column)

# File lib/doku/dancing_links.rb, line 324
def find_or_create_column(id)
  @columns[id] || create_column(id)
end
row(id) click to toggle source

Retrieves a node in the row with the specified ID or returns nil if there is no row with that ID. @param id (Object) The ID of the row that was specified when

{#add_row} was called.

@return (Node)

# File lib/doku/dancing_links.rb, line 408
def row(id)
  @rows[id]
end

Protected Instance Methods

backtrack!(nodes) click to toggle source

This is used by each_exact_cover. Picks the next node to try by back-tracking until we get to a column where we haven’t tried all the nodes, uncovering nodes and columns as it goes. Returns nil if we are done searching the entire solution space.

# File lib/doku/dancing_links.rb, line 534
def backtrack!(nodes)
  while true
    return nil if nodes.empty?  # backtracked back to 0, so we are done
    
    # We tried nodes.last and it didn't work, so
    # pop it off and uncover the corresponding columns.
    node = nodes.pop
    node.unchoose_except_self_column
    
    # Try the next node in this column.
    x = node.down

    return x unless x.is_a? Column
    
    # Our downwards iteration has gone full-circle
    # back to the column object where it started.
    x.uncover   # Uncover the column.
  end
end
choose_column() click to toggle source
# File lib/doku/dancing_links.rb, line 503
def choose_column
  return nil if empty?
  column = smallest_column
  return nil if column.empty?
  return column
end
smallest_column() click to toggle source

When choosing a column, we use Knuth’s S heuristic. Assumption: The matrix has at least one column.

# File lib/doku/dancing_links.rb, line 512
def smallest_column
  # Slow but concise version of this method:
  #return columns.min_by &:size

  column = smallest = right
  min_size = column.size
  while true
    column = column.right
    return smallest if column == self
    
    if column.size < min_size
      smallest, min_size = column, column.size
      return smallest if min_size == 0
    end
  end
end