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
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
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
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
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
Enumerable for all the {Column}s in the matrix.
# File lib/doku/dancing_links.rb, line 294 def columns LinkEnumerator.new :right, self end
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
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
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
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
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
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
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
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
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
# 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
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