Class: Doku::DancingLinks::LinkMatrix

Inherits:
Object
  • Object
show all
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

Classes: Column, Node

Class Method Summary collapse

Instance Method Summary collapse

Methods included from HorizontalLinks

included, #insert_left, #reinsert_horizontal, #remove_horizontal

Methods included from Uninspectable

#inspect

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.

Parameters:

  • sets (Object) —

    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.

  • universe (Array) (defaults to: []) —

    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.

Returns:



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.

Parameters:

  • column_ids (Enumerable) —

    The column_ids that are in this row.

  • row_id (Object) (defaults to: column_ids.dup) —

    The id of this row. This is used to express express exact covers.



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.

Returns:



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 right-most column.

Parameters:

  • id (Object) —

    Any object that uniquely identifies the column.

Returns:

  • (Column) —

    Newly created 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.

Yields:

  • exact_cover

Yield Parameters:

  • exact_cover (Array) —

    Array of row_ids of the rows/sets that are in the cover.



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, 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.

Returns:

  • (Array) —

    Array of row_ids of the rows/sets that are in the cover, or nil if no exact cover was found.



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).

Returns:

  • (Boolean) 


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.

Returns:

  • (Enumerable) —

    Enumerable of exact covers. Each exact cover is an array of row ids of the rows/sets that are in the cover.



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.

Returns:

  • (Array) —

    Array of row ids of the rows/sets that are in the cover, or nil if no exact cover was found.



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.

Returns:



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.

Parameters:

  • id (Object) —

    The ID of the row that was specified when #add_row was called.

Returns:



408
409
410
 
# File 'lib/doku/dancing_links.rb', line 408

def row(id)
  @rows[id]
end