Method: LogicTools#expand

Defined in:
lib/logic_tools/logicsimplify_es.rb

#expand(on, off, deadline) ⇒ Object

Expands cover on as long it does not intersects with off.

NOTE: this step requires to find the minimal column set cover of
a matrix, this algorthim can be very slow and is therefore terminate
before an optimal solution is found is a +deadline+ is exceeded.

Returns the resulting cover.



101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/logic_tools/logicsimplify_es.rb', line 101

def expand(on,off,deadline)
    # Step 1: sort the cubes by weight.
    on = order(on)
    # print "#3.1 #{Time.now}\n"
    # print "on=[#{on.to_s}]\n"

    # Create the resulting cover.
    cover = Cover.new(*on.each_variable)

    # Step 2: Expand the cubes in order of their weights.
    on.each_cube do |cube|
        # print "#3.2 #{Time.now} cube=#{cube}\n"
        # Builds the blocking matrix
        blocking = cube.blocking_matrix(off)
        # print "blocking=[#{blocking}]\n"
        # Select the smallest minimal column cover of the blocking
        # matrix: it will be the expansion
        col_cover = minimal_column_covers(blocking[1..-1],true,deadline)
        # print "col_cover=#{col_cover}\n"
        # This is the new cube
        bits = "-" * cube.width
        col_cover.each do |col|
            # The first row of the blocking matrix give the actual
            # column of the litteral
            col = blocking[0][col] 
            # bits[col] = cube[col]
            bits.setbyte(col,cube.getbyte(col))
        end
        # print "expand result=#{bits}\n"
        # Create and add the new expanded cube.
        cover << Cube.new(bits,false) # No need to clone bits.
    end

    return cover
end