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.



95
96
97
98
99
100
 
# File 'lib/dancing_links.rb', line 95

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.



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

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.



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/dancing_links.rb', line 110

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.



134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/dancing_links.rb', line 134

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