Class: Doku::DancingLinks::LinkMatrix
 Inherits:

Object
 Object
 Doku::DancingLinks::LinkMatrix
 Includes:
 HorizontalLinks
 Defined in:
 lib/doku/dancing_links.rb
Overview
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.
Defined Under Namespace
Class Method Summary collapse

.from_sets(sets, universe = []) ⇒ LinkMatrix
Creates a new LinkMatrix to represent an exact cover problem.
Instance Method Summary collapse

#add_row(column_ids, row_id = column_ids.dup) ⇒ Object
Adds a row to the matrix.

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

#columns ⇒ Object
Enumerable for all the Columns in the matrix.

#create_column(id) ⇒ Column
Creates a new column with the specified ID and inserts it into the matrix as the rightmost column.

#each_exact_cover {exact_cover ... } ⇒ Object
Searches for exact covers and yields them as it finds them.

#each_exact_cover_recursive(k = 0, o = [], &block) ⇒ Array
This method is equivalent to #each_exact_cover but uses the algorithm described on page 5 of Donald Knuth's paper “Dancing Links”.

#empty? ⇒ Boolean
True if there are no more columns left in the matrix (they were all covered).

#exact_covers ⇒ Enumerable
Returns an enumerable that searches for exact covers as its elements are enumerated.

#find_exact_cover ⇒ Array
Searches for an exact cover.

#find_or_create_column(id) ⇒ Column
Retrieves a column object by its ID or creates a new one if it didn't exist already.

#initialize ⇒ LinkMatrix
constructor
Creates a new, empty matrix with no columns and no rows.

#row(id) ⇒ Node
Retrieves a node in the row with the specified ID or returns nil if there is no row with that ID.
Methods included from HorizontalLinks
included, #insert_left, #reinsert_horizontal, #remove_horizontal
Methods included from Uninspectable
Constructor Details
#initialize ⇒ LinkMatrix
Creates a new, empty matrix with no columns and no rows.
287 288 289 290 291 
# File 'lib/doku/dancing_links.rb', line 287 def initialize @left = @right = self @columns = {} # column_id object => Column @rows = {} # row_id object => Node end 
Class Method Details
.from_sets(sets, universe = []) ⇒ LinkMatrix
Creates a new Doku::DancingLinks::LinkMatrix to represent an 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 Doku::DancingLinks::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.
355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 
# 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 
Instance Method Details
#add_row(column_ids, row_id = column_ids.dup) ⇒ Object
Adds a row to the matrix. If a column_id is not recognized, it will be added to the matrix as a new column.
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 
# 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) ⇒ Column
Retrieves a column object by its ID or returns nil if there is no column with that ID.
317 318 319 
# File 'lib/doku/dancing_links.rb', line 317 def column(id) @columns[id] end 
#columns ⇒ Object
Enumerable for all the Columns in the matrix.
294 295 296 
# File 'lib/doku/dancing_links.rb', line 294 def columns LinkEnumerator.new :right, self end 
#create_column(id) ⇒ Column
Creates a new column with the specified ID and inserts it into the matrix as the rightmost column.
308 309 310 311 312 
# 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 {exact_cover ... } ⇒ Object
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.
474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 
# 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 = [], &block) ⇒ Array
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, nonrecursive 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.
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 
# 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? ⇒ Boolean
True if there are no more columns left in the matrix (they were all covered).
300 301 302 
# File 'lib/doku/dancing_links.rb', line 300 def empty? right == self end 
#exact_covers ⇒ Enumerable
Returns an enumerable that searches for exact covers as its elements are enumerated. NOTE: This method mutates the LinkMatrix.
464 465 466 
# File 'lib/doku/dancing_links.rb', line 464 def exact_covers enum_for :each_exact_cover end 
#find_exact_cover ⇒ Array
Searches for an exact cover. NOTE: This method mutates the LinkMatrix.
455 456 457 
# File 'lib/doku/dancing_links.rb', line 455 def find_exact_cover exact_covers.first end 
#find_or_create_column(id) ⇒ Column
Retrieves a column object by its ID or creates a new one if it didn't exist already.
324 325 326 
# File 'lib/doku/dancing_links.rb', line 324 def find_or_create_column(id) @columns[id]  create_column(id) end 
#row(id) ⇒ Node
Retrieves a node in the row with the specified ID or returns nil if there is no row with that ID.
408 409 410 
# File 'lib/doku/dancing_links.rb', line 408 def row(id) @rows[id] end 