class TestEspresso

Class for testing the implementation of the ESPRESSO algorithm.

Public Class Methods

new(seed = 0, deadline = Float::INFINITY, volume = Float::INFINITY) click to toggle source

Creates the tester with a seed for random generation, a deadline for the simplify steps and a volume before splitting the cover.

# File lib/logic_tools/test_logic_tools.rb, line 20
def initialize(seed = 0, deadline = Float::INFINITY,
                           volume = Float::INFINITY)
    # Ensures ESPRESSO is used.
    load "logic_tools/logicsimplify_es.rb"

    @seed = seed
    @deadline = deadline
    @volume = volume
end

Public Instance Methods

same_truth_table?(cover0,cover1) click to toggle source

Checks if covers have the same truth table.

# File lib/logic_tools/test_logic_tools.rb, line 105
def same_truth_table?(cover0,cover1)
    return false unless cover0.width == cover1.width
    # Check for each entry.
    (2**cover0.width).times do |i|
        return false unless cover0.eval_input(i) == cover1.eval_input(i)
    end
    return true
end
test_espresso(cover) click to toggle source

Tests espresso on a given cover.

# File lib/logic_tools/test_logic_tools.rb, line 157
def test_espresso(cover)
    print "ESPRESSO on cover=[#{cover.to_s}]...\n"
    simple = cover.simplify(@deadline,@volume)
    print "result: [#{simple}]\n"
    # check0 = (cover + simple.complement).is_tautology?
    check0 = same_truth_table?(cover,simple)
    # assert_equal(true,check0)
    print "check 0 = #{check0}\n"
    raise "Test failure" unless check0
    check1 = (cover.complement + simple).is_tautology?
    # assert_equal(true,check1)
    print "check 1 = #{check1}\n"
    raise "Test failure" unless check1
    return true
end
test_espresso_all(test = nil) click to toggle source

Tests the implementation of the espresso algorithm on each possible 1-cube cover of 4 variables.

Test only on cover if a test number is given.

# File lib/logic_tools/test_logic_tools.rb, line 177
def test_espresso_all(test = nil)
    generator = Generator.new("a","b","c","d")
    generator.seed = @seed
    if test then
        test = test.to_i
        print "Test #{test}: "
        return test_espresso(generator.make_1cover(test))
    else
        generator.each_1cover.with_index do |cover,i|
            print "Test #{i}: "
            return false unless test_espresso(cover)
        end
        return true
    end
end
test_espresso_random(generator) click to toggle source

Tests ESPRESSO on a cover generated by a random generator.

# File lib/logic_tools/test_logic_tools.rb, line 194
def test_espresso_random(generator)
    # Genrate a random cover.
    cover = generator.random_cover
    # Test it.
    return false unless test_espresso(cover)
    return true
end
test_espressos_random(number = 1024, dimensions = 4, max = nil) click to toggle source

Tests ESPRESSO on randomly number cover cases on a dimensions boolean space, including at most max cubes.

# File lib/logic_tools/test_logic_tools.rb, line 204
def test_espressos_random(number = 1024, dimensions = 4, max = nil)
    # Create the variables.
    base = "`"
    variables = dimensions.times.map { |i| base.next!.clone }
    # Create the generator.
    generator = Generator.new(*variables)
    generator.seed = @seed
    generator.max = max if max
    # Ensures a rate of "-" large enough to have a high probability of
    # an interesting cover (i.e., which is actually simplifiable).
    # This rate +r+ is obainted as the solution of the followings:
    # max/2 * 2**(r*dimensions) >= 2**dimensions
    # NOTE: max/2 is the average size of the cover.
    generator.rate = Math::log2(2**(dimensions+1)/max.to_f)/dimensions
    # Ensures the rate is not too small though.
    generator.rate = 0.3 unless generator.rate >= 0.3
    print "rate=#{generator.rate}\n"
    # Performs the tests.
    number.times do |i|
        print "Test #{i}: "
        return false unless test_espresso_random(generator)
    end
    return true
end
test_qm(tree) click to toggle source

Tests Quine Mac Cluskey on a given tree.

# File lib/logic_tools/test_logic_tools.rb, line 116
def test_qm(tree)
    print "Quine Mc Cluskey algorithm on expression=[#{tree}]...\n"
    simple = tree.simplify()
    print "result: [#{tree}]\n"
    cover = tree.to_cover
    check0 = (cover + simple.complement).is_tautology?
    # check0 = same_truth_table?(cover,simple)
    # assert_equal(true,check0)
    print "check 0 = #{check0}\n"
    raise "Test failure" unless check0
    check1 = (cover.complement + simple).is_tautology?
    # assert_equal(true,check1)
    print "check 1 = #{check1}\n"
    raise "Test failure" unless check1
    return true
end
test_qm_all(test = nil) click to toggle source

Tests the implementation of the espresso algorithm on each possible 1-cube cover of 4 variables.

Test only on cover if a test number is given.

# File lib/logic_tools/test_logic_tools.rb, line 137
def test_qm_all(test = nil)
    generator = Generator.new("a","b","c","d")
    generator.seed = @seed
    if test then
        test = test.to_i
        print "Test #{test}: "
        return test_qm(generator.make_std_conj(test))
    else
        generator.each_std_conj.with_index do |tree,i|
            print "Test #{i}: "
            return false unless test_qm(tree)
        end
        return true
    end
end
test_tautologies_random(number = 1024, dimensions = 4) click to toggle source

Tests randomly number tautology cases on a dimensions boolean space.

# File lib/logic_tools/test_logic_tools.rb, line 65
def test_tautologies_random(number = 1024, dimensions = 4)
    # Create the variables.
    base = "`"
    variables = dimensions.times.map { |i| base.next!.clone }
    # Create the generator.
    generator = Generator.new(*variables)
    generator.seed = @seed
    # Performs the tests.
    number.times do |i|
        print "Test #{i}: "
        return false unless test_tautology_random(generator)
    end
    return true
end
test_tautology_random(generator) click to toggle source

Tests the tautology check on covers generated by a random generator.

NOTE: ends when a tautology is actually found.

# File lib/logic_tools/test_logic_tools.rb, line 42
def test_tautology_random(generator)
    # Create the cover.
    cover = Cover.new(*generator.each_variable)
    # Tautology results.
    taut0, taut1 = false, false
    # Add random cubes to the cover until a tautology is met while.
    begin
        # Add a random cube.
        cover << generator.random_cube
        print "Tautology check on cover=[#{cover.to_s}]...\n"
        # Check if the cover is a tautology using the standard approach.
        taut0 = cover.is_tautology?
        print "Through is_tautology?: #{taut0}; "
        # Check it again with a truth table.
        taut1 = truth_tautology(cover)
        print "through truth table: #{taut1}\n"
        raise "Test failure" unless taut0 == taut1
    end while (!taut0)
    return true
end
truth_tautology(cover) click to toggle source

Checks if a cover is a tautology by generating its truth table.

# File lib/logic_tools/test_logic_tools.rb, line 31
def truth_tautology(cover)
    ## Generate each possible input and test it on the cover.
    (2**(cover.width)).times do |i|
        return false unless cover.eval_input(i)
    end
    return true
end