Class: DancingLinks::SparseMatrix

Inherits:
Object
  • Object
show all
Defined in:
lib/dancing_links.rb

Overview

This class is used internally by the “Dancing Links” algorithm.

This “matrix” contains nodes for all of the “1”s of the matrix. The nodes linked together in a doubly-linked chain both horizontally and vertically. Each column in the matrix has a header node, and the column headers have a “header” called the root.

The headers, links, counters, etc… all serve to do the “book keeping” of the algorithm so that columns/rows can quickly be removed/replaced while the search occuring.

The algorithm is essentially a depth-first search (aka backtracking) with the matrix facilitating the neccessary operations.

Defined Under Namespace

Classes: SparseMatrixHeader, SparseMatrixNode, SparseMatrixRoot

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(matrix) ⇒ SparseMatrix

creates the root node and calls build_sparse_matrix to construct the matrix.

* matrix - an array of boolean arrays.  This array represents the available rows from which the algorithm must choose.



145
146
147
148
149
150
 
# File 'lib/dancing_links.rb', line 145

def initialize matrix
  #puts "init"
  @root = SparseMatrixRoot.new
  build_sparse_matrix(matrix)
  #puts "end-init"
end

Instance Attribute Details

#root ⇒ Object

Returns the value of attribute root.



197
198
199
 
# File 'lib/dancing_links.rb', line 197

def root
  @root
end

Instance Method Details

#build_sparse_matrix(matrix) ⇒ Object

Iterates through the matrix (an array of boolean arrays). When finding a “true”

value, it constructs a node and places the node appropriately within the matrix.

Note that any columns (from the array) which contain no "true" values will simply
be ignored.  The algorithm will still attempt to find a solution for the existing
columns.



160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/dancing_links.rb', line 160

def build_sparse_matrix(matrix)
  matrix.each_index do |i|
    row = matrix[i]
    row_node = nil
    row.each_index do |j|
      if row[j]
        header = get_column_header j
        if row_node
          row_node = node =
            SparseMatrixNode.new( i, header, row_node, row_node.right, header.up, header)
        else
          node =
            SparseMatrixNode.new( i, header, nil, nil, header.up, header)
          row_node= node.left= node.right= node
        end
      end
    end
  end
end

#get_column_header(index) ⇒ Object

A utility for build_sparse_matrix. Finds and/or constructs (if needed) the header

node for a given column.



184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/dancing_links.rb', line 184

def get_column_header index
  header = @root.right
  
  while header != @root && header.index <= index
    if header.index == index
      return header
    end
    header = header.right
  end
  new_header = SparseMatrixHeader.new( index, @root, header.left, header)

end