From 7b34bab6af30df9cfca7df9e0c644a0ea967ff04 Mon Sep 17 00:00:00 2001 From: sucanjan Date: Wed, 14 Feb 2018 21:57:30 +0100 Subject: Initial commit --- .rubocop.yml | 2 + Gemfile | 4 + LICENSE | 19 ++ Rakefile | 13 + bin/knapsack_solver | 12 + knapsack_solver.gemspec | 33 +++ lib/knapsack_solver.rb | 2 + lib/knapsack_solver/cli.rb | 49 ++++ lib/knapsack_solver/cli_option_checker.rb | 83 +++++++ lib/knapsack_solver/cli_option_parser.rb | 68 ++++++ lib/knapsack_solver/dataset.rb | 44 ++++ lib/knapsack_solver/graph_printer.rb | 115 +++++++++ lib/knapsack_solver/instance.rb | 48 ++++ lib/knapsack_solver/output_printer.rb | 97 ++++++++ lib/knapsack_solver/solver.rb | 118 ++++++++++ .../solving_methods/branch_and_bound.rb | 111 +++++++++ .../solving_methods/dynamic_programming.rb | 116 +++++++++ lib/knapsack_solver/solving_methods/fptas.rb | 47 ++++ .../solving_methods/heuristic_price_weight.rb | 56 +++++ lib/knapsack_solver/version.rb | 5 + test/datasets/size_10.dataset | 4 + test/datasets/size_4.dataset | 4 + test/invalid_datasets/invalid_1.dataset | 0 test/invalid_datasets/invalid_2.dataset | 3 + test/invalid_datasets/invalid_3.dataset | 4 + test/invalid_datasets/invalid_4.dataset | 4 + test/invalid_datasets/invalid_5.dataset | 2 + test/invalid_datasets/invalid_6.dataset | 2 + test/invalid_datasets/invalid_7.dataset | 4 + test/invalid_datasets/invalid_8.dataset | 4 + test/knapsack_solver_matchers.rb | 103 ++++++++ test/knapsack_solver_spec.rb | 261 +++++++++++++++++++++ .../size_10_dynamic_programming.results | 5 + test/output_logs/size_10_dynamic_programming.stats | 3 + test/output_logs/size_10_fptas.results | 5 + test/output_logs/size_10_fptas.stats | 3 + test/output_logs/size_10_heuristic.results | 5 + test/output_logs/size_10_heuristic.stats | 3 + .../output_logs/size_4_dynamic_programming.results | 5 + test/output_logs/size_4_dynamic_programming.stats | 3 + test/output_logs/size_4_fptas.results | 5 + test/output_logs/size_4_fptas.stats | 3 + test/output_logs/size_4_heuristic.results | 5 + test/output_logs/size_4_heuristic.stats | 3 + test/spec_helper.rb | 5 + 45 files changed, 1490 insertions(+) create mode 100644 .rubocop.yml create mode 100644 Gemfile create mode 100644 LICENSE create mode 100644 Rakefile create mode 100644 bin/knapsack_solver create mode 100644 knapsack_solver.gemspec create mode 100644 lib/knapsack_solver.rb create mode 100644 lib/knapsack_solver/cli.rb create mode 100644 lib/knapsack_solver/cli_option_checker.rb create mode 100644 lib/knapsack_solver/cli_option_parser.rb create mode 100644 lib/knapsack_solver/dataset.rb create mode 100644 lib/knapsack_solver/graph_printer.rb create mode 100644 lib/knapsack_solver/instance.rb create mode 100644 lib/knapsack_solver/output_printer.rb create mode 100644 lib/knapsack_solver/solver.rb create mode 100644 lib/knapsack_solver/solving_methods/branch_and_bound.rb create mode 100644 lib/knapsack_solver/solving_methods/dynamic_programming.rb create mode 100644 lib/knapsack_solver/solving_methods/fptas.rb create mode 100644 lib/knapsack_solver/solving_methods/heuristic_price_weight.rb create mode 100644 lib/knapsack_solver/version.rb create mode 100644 test/datasets/size_10.dataset create mode 100644 test/datasets/size_4.dataset create mode 100644 test/invalid_datasets/invalid_1.dataset create mode 100644 test/invalid_datasets/invalid_2.dataset create mode 100644 test/invalid_datasets/invalid_3.dataset create mode 100644 test/invalid_datasets/invalid_4.dataset create mode 100644 test/invalid_datasets/invalid_5.dataset create mode 100644 test/invalid_datasets/invalid_6.dataset create mode 100644 test/invalid_datasets/invalid_7.dataset create mode 100644 test/invalid_datasets/invalid_8.dataset create mode 100644 test/knapsack_solver_matchers.rb create mode 100644 test/knapsack_solver_spec.rb create mode 100644 test/output_logs/size_10_dynamic_programming.results create mode 100644 test/output_logs/size_10_dynamic_programming.stats create mode 100644 test/output_logs/size_10_fptas.results create mode 100644 test/output_logs/size_10_fptas.stats create mode 100644 test/output_logs/size_10_heuristic.results create mode 100644 test/output_logs/size_10_heuristic.stats create mode 100644 test/output_logs/size_4_dynamic_programming.results create mode 100644 test/output_logs/size_4_dynamic_programming.stats create mode 100644 test/output_logs/size_4_fptas.results create mode 100644 test/output_logs/size_4_fptas.stats create mode 100644 test/output_logs/size_4_heuristic.results create mode 100644 test/output_logs/size_4_heuristic.stats create mode 100644 test/spec_helper.rb diff --git a/.rubocop.yml b/.rubocop.yml new file mode 100644 index 0000000..bf31b8e --- /dev/null +++ b/.rubocop.yml @@ -0,0 +1,2 @@ +Metrics/LineLength: + Max: 120 diff --git a/Gemfile b/Gemfile new file mode 100644 index 0000000..4c5c0c9 --- /dev/null +++ b/Gemfile @@ -0,0 +1,4 @@ +source 'https://rubygems.org' + +# Dependencies of this gem are in .gemspec. +gemspec diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..4af7772 --- /dev/null +++ b/LICENSE @@ -0,0 +1,19 @@ +Copyright (c) 2018, Ján Sučan + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/Rakefile b/Rakefile new file mode 100644 index 0000000..9a5f79e --- /dev/null +++ b/Rakefile @@ -0,0 +1,13 @@ +require 'rake' +require 'rspec/core/rake_task' +require 'rubocop/rake_task' + +RSpec::Core::RakeTask.new(:spec) do |t| + t.pattern = Dir.glob('test/**/*_spec.rb') +end + +RuboCop::RakeTask.new(:rubocop) do |t| + t.patterns = Dir.glob('lib/**/*.rb') +end + +task default: :spec diff --git a/bin/knapsack_solver b/bin/knapsack_solver new file mode 100644 index 0000000..2e2de9d --- /dev/null +++ b/bin/knapsack_solver @@ -0,0 +1,12 @@ +#!/usr/bin/env ruby + +require 'knapsack_solver/cli' + +begin + KnapsackSolver::CLI.run(ARGV) + exit 0 +rescue StandardError => e + STDERR.puts "ERROR: #{e.message}" + STDERR.puts "Try 'knapsack_solver --help' for more information." + exit 1 +end diff --git a/knapsack_solver.gemspec b/knapsack_solver.gemspec new file mode 100644 index 0000000..8a3bf4d --- /dev/null +++ b/knapsack_solver.gemspec @@ -0,0 +1,33 @@ +require File.expand_path('lib/knapsack_solver/version', __dir__) + +Gem::Specification.new do |s| + s.name = 'knapsack_solver' + s.version = KnapsackSolver::VERSION + s.homepage = 'https://github.com/sucanjan/knapsack-solver' + s.license = 'MIT' + s.author = 'Jan Sucan' + s.email = 'sucanjan@fit.cvut.cz' + + s.summary = '0/1 knapsack problem solver.' + s.description = <<-EOF +This gem contains command-line utility for solving 0/1 knapsack problem using +branch-and-bound method, dynamic programming, simple heuristic (weight/price) +and fully polynomial time approximation scheme. + +It can measure CPU and wall-clock time spent by solving a problem, compute +relative error of the result and generate graphs from those values. +EOF + + s.files = Dir['bin/*', 'lib/**/*', '*.gemspec', 'LICENSE*', 'README*', 'test/*'] + s.executables = Dir['bin/*'].map { |f| File.basename(f) } + s.has_rdoc = 'yard' + + s.required_ruby_version = '>= 2.2' + + s.add_runtime_dependency 'gnuplot', '~> 2.6' + + s.add_development_dependency 'rake', '~> 12.0' + s.add_development_dependency 'rspec', '~> 3.6' + s.add_development_dependency 'rubocop', '~> 0.50.0' + s.add_development_dependency 'yard', '~> 0.9' +end diff --git a/lib/knapsack_solver.rb b/lib/knapsack_solver.rb new file mode 100644 index 0000000..9d5f19f --- /dev/null +++ b/lib/knapsack_solver.rb @@ -0,0 +1,2 @@ +require 'knapsack_solver/version' +require 'knapsack_solver/solver' diff --git a/lib/knapsack_solver/cli.rb b/lib/knapsack_solver/cli.rb new file mode 100644 index 0000000..716fb08 --- /dev/null +++ b/lib/knapsack_solver/cli.rb @@ -0,0 +1,49 @@ +require 'knapsack_solver/solver' +require 'knapsack_solver/version' +require 'knapsack_solver/cli_option_parser' +require 'knapsack_solver/output_printer' +require 'knapsack_solver/graph_printer' + +module KnapsackSolver + # This class implements a command-line interface for the 0/1 knapsack + # problem solver. + class CLI + # Suffix of a text file which will containg results of dataset solving + # (price, knapsack things presence, cpu time, wall clock time, + # relative_error). + RESULTS_FILNEMAE_SUFFIX = '.results'.freeze + + # Suffix of a text file which will containg statistic data (average price, + # execution times, relative error) + STATS_FILNEMAE_SUFFIX = '.stats'.freeze + + # Processes command-line arguments. If no option is given, converts arabic + # number to roman number and prints it to stdout. + # + # @param args [Array] the command-line arguments + def self.run(args) + options = CliOptionParser.parse(args) + return if options.nil? + datasets = args.each_with_object([]) do |file, sets| + sets << Dataset.parse(File.new(file)) + end + s = Solver.new(options, datasets) + results = s.run + print_results(results, s.stats(results), options, args) + end + + # Prints output of datasets solving. Results and statistics are printed to + # stdout or to a text files. Graphs of statistic values can be created. + # + # @param results [Hash] results of dataset solvings + # @param stats [Hash] statistics from the results of dataset solvings + # @param options [Hash] Command-line line options supplied to the CLI + # @param args [Array] array of the positional command-line arguments + def self.print_results(results, stats, options, args) + OutputPrinter.new(args, RESULTS_FILNEMAE_SUFFIX, results).print(options[:output_dir]) + OutputPrinter.new(args, STATS_FILNEMAE_SUFFIX, stats).print(options[:output_dir]) + return unless options[:graphs_dir] + GraphPrinter.new(args, stats, options[:graphs_dir]).print + end + end +end diff --git a/lib/knapsack_solver/cli_option_checker.rb b/lib/knapsack_solver/cli_option_checker.rb new file mode 100644 index 0000000..f55dca2 --- /dev/null +++ b/lib/knapsack_solver/cli_option_checker.rb @@ -0,0 +1,83 @@ +require 'optparse' + +module KnapsackSolver + # This class checks command line arguments provided to the knapsack_solver + # binary. + class CliOptionChecker + # Checks command-line options, their arguments and positional arguments + # provided to the CLI. + # + # @param opts [Hash] parsed command-line options + # @param args [Array] command-line positional arguments + def self.check(opts, args) + if !opts[:branch_and_bound] && !opts[:dynamic_programming] && + !opts[:fptas] && !opts[:heuristic] + raise StandardError, 'At least one method of solving must be requested' + end + check_fptas_options(opts) + check_directories(opts) + check_positional_arguments(args) + end + + # Checks command-line options and arguments used by FPTAS solving method. + # + # @param opts [Hash] parsed command-line options + def self.check_fptas_options(opts) + return if !opts[:fptas] && !opts.key?(:fptas_epsilon) + check_incomplete_fptas_options(opts) + eps = opts[:fptas_epsilon].to_f + return unless eps <= 0 || eps >= 1 || eps.to_s != opts[:fptas_epsilon] + raise StandardError, + 'FPTAS epsilon must be number from range (0,1)' + end + + # Checks command-line options and arguments used by FPTAS solving + # method. Recignizes cases when mandatory FPTAS epsilon constant is + # missing or when it the constant is provided and FPTAS method is not + # requested. + # + # @param opts [Hash] parsed command-line options + def self.check_incomplete_fptas_options(opts) + raise StandardError, 'Missing FPTAS epsilon constant' if opts[:fptas] && !opts.key?(:fptas_epsilon) + return unless !opts[:fptas] && opts.key?(:fptas_epsilon) + raise StandardError, + 'epsilon constant must not be provided when FPTAS is not selected' + end + + # Checks directory for result and statistic output logs, and directory for + # graph files. + # + # @param opts [Hash] parsed command-line options + def self.check_directories(opts) + check_output_directory(opts[:output_dir]) if opts[:output_dir] + check_output_directory(opts[:graphs_dir]) if opts[:graphs_dir] + end + + # Checks if at least one dataset input file was provided and if the input + # files are readable. + # + # @param args [Array] positional arguments provided to the CLI + def self.check_positional_arguments(args) + raise StandardError, 'Missing datset file(s)' if args.empty? + args.each { |f| check_input_file(f) } + end + + # Checks if an output directory exist and is writable. + # + # @param path [Path] path to output directory + def self.check_output_directory(path) + raise StandardError, "Directory '#{path}' does not exists" unless File.exist?(path) + raise StandardError, "'#{path}' is not a directory" unless File.directory?(path) + raise StandardError, "Directory '#{path}' is not writable" unless File.writable?(path) + end + + # Checks if an input file exist and is readable. + # + # @param path [Path] path to input regular file + def self.check_input_file(path) + raise StandardError, "File '#{path}' does not exists" unless File.exist?(path) + raise StandardError, "'#{path}' is not a regular file" unless File.file?(path) + raise StandardError, "File '#{path}' is not readable" unless File.readable?(path) + end + end +end diff --git a/lib/knapsack_solver/cli_option_parser.rb b/lib/knapsack_solver/cli_option_parser.rb new file mode 100644 index 0000000..0f0720c --- /dev/null +++ b/lib/knapsack_solver/cli_option_parser.rb @@ -0,0 +1,68 @@ +require 'optparse' +require 'knapsack_solver/cli_option_checker' + +module KnapsackSolver + # This class parses command line arguments provided to the knapsack_solver + # binary. + class CliOptionParser + # Message that describes how to use this CLI utility. + USAGE_MESSAGE = 'Usage: knapsack_solver OPTIONS DATASET_FILE...'.freeze + + # Parses command-line arguments and removes them from the array of + # arguments. + # + # @param [Array] arguments the command-line arguments. + # @return [Hash] hash of recognized options. + # + # rubocop:disable Metrics/AbcSize, Metric/MethodLength, Metric/BlockLength + def self.parse(arguments) + options = {} + parser = OptionParser.new do |opts| + opts.banner = USAGE_MESSAGE + opts.on('-b', '--branch-and-bound', 'Use branch and boung method of solving') do + options[:branch_and_bound] = true + end + opts.on('-d', '--dynamic-programming', 'Use dynamic programming for solving') do + options[:dynamic_programming] = true + end + opts.on('-f', '--fptas', 'Use FPTAS for solving') do + options[:fptas] = true + end + opts.on('-r', '--heuristic', 'Use brute force method of solving') do + options[:heuristic] = true + end + opts.on('-e', '--fptas-epsilon EPS', 'Relative error for FPTAS from range (0,1)') do |eps| + options[:fptas_epsilon] = eps + end + opts.on('-o', '--output DIR', 'Directory for output log files') do |dir| + options[:output_dir] = dir + end + opts.on('-g', '--graphs DIR', 'Directory for graphs') do |dir| + options[:graphs_dir] = dir + end + opts.on('-v', '--version', 'Show program version') do + options[:version] = true + end + opts.on_tail('-h', '--help', 'Show this help message') do + options[:help] = true + end + end + parser.parse!(arguments) + process_help_and_version_opts(options, arguments, parser.to_s) + end + # rubocop:enable Metrics/AbcSize, Metric/MethodLength, Metric/BlockLength + + def self.process_help_and_version_opts(options, arguments, usage_msg) + if !options[:help] && !options[:version] + CliOptionChecker.check(options, arguments) + return options + end + if options[:help] + puts usage_msg + elsif options[:version] + puts "knapsack_solver #{KnapsackSolver::VERSION}" + end + nil + end + end +end diff --git a/lib/knapsack_solver/dataset.rb b/lib/knapsack_solver/dataset.rb new file mode 100644 index 0000000..b38e9e5 --- /dev/null +++ b/lib/knapsack_solver/dataset.rb @@ -0,0 +1,44 @@ +require 'knapsack_solver/instance' + +module KnapsackSolver + # This class represents a set of 0/1 knapsack problem instances. + class Dataset + # Initializes set of 0/1 knapsack problem instances. + # + # @param id [Integer] Dataset ID number. + # @param instances [Array] set of the 0/1 knapsack problem instances. + def initialize(id, instances) + @id = id + @instances = instances + end + + # Parses set of a 0/1 knapsack problem instances from a character stream. + # + # @param stream [#eof?,#readline,#each_line] character stream holding the dataset. + # @return [Dataset] dataset instance parsed from the stream. + def self.parse(stream) + id = parse_id(stream) + instances = stream.each_line.with_object([]) { |l, o| o << Instance.parse(l) } + raise StandardError, 'dataset: missing instances' if instances.empty? + Dataset.new(id, instances) + end + + # Parses ID of a 0/1 knapsack problem dataset from a character stream. + # + # @param stream [#eof?,#readline,#each_line] character stream holding the dataset. + # @return [Integer] dataset ID number. + def self.parse_id(stream) + raise StandardError, 'dataset: missing ID' if stream.eof? + s = stream.readline.split + raise StandardError, 'dataset: first line does not contain ID' if s.size != 1 + begin + raise StandardError, 'dataset: ID is negative' if Integer(s.first) < 0 + rescue ArgumentError + raise StandardError, 'dataset: ID is not an integer' + end + Integer(s.first) + end + + attr_reader :id, :instances + end +end diff --git a/lib/knapsack_solver/graph_printer.rb b/lib/knapsack_solver/graph_printer.rb new file mode 100644 index 0000000..318e02e --- /dev/null +++ b/lib/knapsack_solver/graph_printer.rb @@ -0,0 +1,115 @@ +require 'gnuplot' + +module KnapsackSolver + # This class provides support for making graphs from statistics of datasets + # solving results. It uses Gnuplot and also generates a Gnuplot config file + # for each generated graph. + class GraphPrinter + # Initializes printer for graph data (graphs, Gnuplot config files). + # + # @param dataset_filenames [Array] dataset filenames + # @param stats [Hash] statistics of results + # @param out_dir [String] statistics of results to print + def initialize(dataset_filenames, stats, out_dir) + @dataset_basenames = file_basenames(dataset_filenames) + @stats = stats + @out_dir = out_dir + end + + # Create graphs from statistics and Gnuplot configuration files. + def print + stats_to_datasets.each do |title, ds| + ofn = File.join(@out_dir, title + '.png') + plot(title, ds, ofn) + end + end + + protected + + # Create graph. + # + # @param title [String] title of the graph + # @param data [Array] Gnuplot datasets to plot + # @param filename [String] path to the output image file + def plot(title, data, filename) + Gnuplot.open do |gp| + Gnuplot::Plot.new(gp, &plot_config(title, 'dataset', 'y', data, filename)) + end + File.open(File.join(File.dirname(filename), File.basename(filename, '.png') + '.gnuplot'), 'w') do |gp| + Gnuplot::Plot.new(gp, &plot_config(title, 'dataset', 'y', data, filename)) + end + end + + # Creates Gnuplot datasets from statistics. + # + # @return [Array] Gnuplot datasets created from the statistics. + def stats_to_datasets + graphs = @stats.values.first.values.first.first.keys + x_data = @stats.keys + datasets(graphs, x_data) + end + + # Creates Gnuplot datasets from statistics. + # + # @param graphs [Array] array of graph titles + # @param x_data [Array] array of X axis values + def datasets(graphs, x_data) + graphs.each_with_object({}) do |g, gnuplot_datasets| + @stats.each_value do |s| + gnuplot_datasets[g.to_s] = s.each_key.with_object([]) do |method, o| + o << plot_dataset(method.to_s, x_data, @stats.map { |_, v| v[method].first[g] }) + end + end + end + end + + # Create dataset from provided title, X axis data and Y axis data. + # + # @param title [String] Gnuplot dataset title + # @param x_data [Array] Array of X values + # @param y_data [Array] Array of Y values + # @return [Gnuplot::DataSet] Gnuplot dataset. + def plot_dataset(title, x_data, y_data) + Gnuplot::DataSet.new([x_data, y_data]) { |ds| ds.title = escape_gnuplot_special_chars(title) } + end + + # Creates Gnuplot plot configuration (configuration text lines). + # + # @param title [String] graph title + # @param xlabel [String] label of X axis + # @param ylabel [String] label of Y axis + # @param plot_datasets [Array] Gnuplot datasets for plotting + # @param out_file [String] output file + # @return [lambda] Lambda for setting plot configuration. + def plot_config(title, xlabel, ylabel, plot_datasets, out_file) + lambda do |plot| + plot.term('png') + plot.output(out_file) + plot.title("'#{escape_gnuplot_special_chars(title)}'") + plot.ylabel("'#{escape_gnuplot_special_chars(ylabel)}'") + plot.xlabel("'#{escape_gnuplot_special_chars(xlabel)}'") + plot.key('outside') + plot.data = plot_datasets + end + end + + # Escapes Gnuplot special characters. + # + # @param str [String] a string + # @return [Strnig] the string with Gnuplot special chars escaped + def escape_gnuplot_special_chars(str) + # underscore means subscript in Gnuplot + str.gsub('_', '\_') + end + + # Gets basenames of supplied file paths. + # + # @param paths [Array] path to files + # @return [Array] basenames of the paths + def file_basenames(paths) + paths.each_with_object([]) do |path, basenames| + basenames << File.basename(path, File.extname(path)) + end + end + end +end diff --git a/lib/knapsack_solver/instance.rb b/lib/knapsack_solver/instance.rb new file mode 100644 index 0000000..1fe3ecc --- /dev/null +++ b/lib/knapsack_solver/instance.rb @@ -0,0 +1,48 @@ +module KnapsackSolver + # This class represents an instance of a 0/1 knapsack problem. + class Instance + # Initializes instance of a 0/1 knapsack problem. + # + # @param capacity [Integer] weight capacity of the knapsack + # @param things [Array] things which can be put into the knapsack + def initialize(capacity, things) + @weight_capacity = capacity + @things = things + end + + # Creates new instance of a 0/1 knapsack problem. + # + # @param line [String] line that describes an instance of a 0/1 knapsack problem + # @return [Instance] instance of the 0/1 knapsack problem + def self.parse(line) + thing = Struct.new(:price, :weight, :index) + # Rozdelit riadok na slova a previest na cisla + items = split_line(line) + # Inicializacia premennych + things = items.drop(1).each_slice(2).with_index.each_with_object([]) do |(s, i), o| + o << thing.new(s[0], s[1], i) + end + Instance.new(items[0], things) + end + + # Splits line that describes an instance of a 0/1 knapsack problem to + # individual numbers. + # + # @param line [String] line that describes an instance of a 0/1 knapsack problem + # @return [Array] integer numbers from the line + def self.split_line(line) + items = line.split.map! do |i| + n = Integer(i) + raise StandardError, 'dataset: instance desctiption contains negative number' if n < 0 + n + end + raise StandardError, 'dataset: missing knapsack capacity' if items.empty? + raise StandardError, 'dataset: missing pairs (price, weight)' if items.size.even? + items + rescue ArgumentError + raise StandardError, 'dataset: instance desctiption does not contain only integers' + end + + attr_reader :weight_capacity, :things + end +end diff --git a/lib/knapsack_solver/output_printer.rb b/lib/knapsack_solver/output_printer.rb new file mode 100644 index 0000000..8ed857a --- /dev/null +++ b/lib/knapsack_solver/output_printer.rb @@ -0,0 +1,97 @@ +module KnapsackSolver + # This class provides support for printing results and statistics of a + # dataset solving either to stdout or to a text file. + class OutputPrinter + # Initializes printer for output log (results, statistics). + # + # @param dataset_filenames [Array] dataset filenames + # @param suffix [String] suffix of the created files + # @param results [Hash] results of solving or statistics to print + def initialize(dataset_filenames, suffix, results) + @dataset_basenames = file_basenames(dataset_filenames) + @suffix = suffix + @results = results + end + + # Prints results or statistics to stdout or to files in output directory. + # + # @param out_dir [String] path to output directory + def print(out_dir = nil) + @results.each_value.with_index do |results, index| + results.each do |method, res| + print_solving_method_results(method, res, out_dir, @dataset_basenames[index]) + end + end + end + + protected + + # Prints results of solving or statistics. + # + # @param method [Symbol] symbol for solving method + # @param res [Hash] results of the solving method + # @param out_dir [String] path to output directory + # @param basename [String] basename of dataset input file corresponding to the results + def print_solving_method_results(method, res, out_dir, basename) + of = output_filename(out_dir, basename, method.to_s) + os = output_stream(out_dir, of) + print_header(os, of, res) + res.each do |r| + os.puts r.values.each_with_object([]) { |v, a| a << v.to_s }.join(' ') + end + os.puts if out_dir.nil? + end + + # Opens output file and turns on synchronized writes (this is neede for + # testing with Rspec). + # + # @param fname [String] path to the output file + # @return [#puts] output stream + def open_output_file(fname) + f = File.new(fname, 'w') + f.sync = true + f + end + + # Sets output stream to stdout or to a file if path to it was provided. + # + # @param out_dir [String] directory for output files + # @param out_file [String] output file + def output_stream(out_dir, out_file) + return $stdout if out_dir.nil? + open_output_file(out_file) + end + + # Prints header of output log file. + # + # @param out_stream [#puts] stream to which output will be printed + # @param out_file [String] name of output file + # @param results [Hash] results of solving or statistics + def print_header(out_stream, out_file, results) + out_stream.puts "# #{out_file}" + out_stream.puts "# #{results.first.keys.join(' ')}" + end + + # Gets basenames of supplied file paths. + # + # @param paths [Array] path to files + # @return [Array] basenames of the paths + def file_basenames(paths) + paths.each_with_object([]) do |path, basenames| + basenames << File.basename(path, File.extname(path)) + end + end + + # Construct filename for output log. + # + # @param output_dir [String] output directory + # @param basename [String] basename of the output file + # @param solving_method [String] name of solving method + # @return [String] filename for output log + def output_filename(output_dir, basename, solving_method) + filename = basename + '_' + solving_method + @suffix + return filename if output_dir.nil? + File.join(output_dir, filename) + end + end +end diff --git a/lib/knapsack_solver/solver.rb b/lib/knapsack_solver/solver.rb new file mode 100644 index 0000000..c392d69 --- /dev/null +++ b/lib/knapsack_solver/solver.rb @@ -0,0 +1,118 @@ +require 'benchmark' + +require 'knapsack_solver/dataset' +require 'knapsack_solver/solving_methods/heuristic_price_weight' +require 'knapsack_solver/solving_methods/branch_and_bound' +require 'knapsack_solver/solving_methods/dynamic_programming' +require 'knapsack_solver/solving_methods/fptas' + +module KnapsackSolver + # This class solves datasets of 0/1 knapsack problem instances using a + # requested solving methods. It measures execution time of a solving and + # computes relative error if some exact solving method is requested. + class Solver + # Initializes solver for use of user selected solving methods. + # + # @param opts [Hash] parser command-line options + # @param datasets [Hash] parsed sets of 0/1 knapsack problem instances + def initialize(opts, datasets) + @opts = opts + @datasets = datasets + @solver_objects = {} + { branch_and_bound: 'KnapsackSolver::BranchAndBound', + dynamic_programming: 'KnapsackSolver::DynamicProgramming', + heuristic: 'KnapsackSolver::HeuristicPriceToWeight', + fptas: 'KnapsackSolver::Fptas' }.each do |symbol, class_name| + @solver_objects[symbol] = Object.const_get(class_name) if opts[symbol] + end + end + + # Solve datasets using all selected method of solving, measure their + # execution time and compute relative errors if some exact method was + # requested. + # + # @return [Hash] results of dataset solving + def run + results = @datasets.each_with_object({}) do |dataset, res| + res[dataset.id] = @solver_objects.each_with_object({}) do |(solver, object), r| + r[solver] = dataset.instances.each_with_object([]) do |inst, a| + o = object.new(inst) unless solver == :fptas + o = object.new(inst, @opts[:fptas_epsilon]) if solver == :fptas + a << execution_time { o.run } + end + end + end + add_relative_error(results) + end + + # Creates statistics (average price, execution times, relative error) from + # results of solving. + # + # @param results [Hash] solving results of datasets and solving methods + # @return [Hash] statistics for datasets and solving methods + def stats(results) + results.each_with_object({}) do |(dataset_id, method_results), q| + q[dataset_id] = method_results.each_with_object({}) do |(met, res), p| + p[met] = averages(res) + end + end + end + + protected + + # Computes average values from the results. + # + # @param res [Hash] results for one dataset and one method + # @return [Array] array of computed average values + def averages(res) + [res.first.keys.reject { |k| k == :config }.each_with_object({}) do |v, o| + values = res.map { |i| i[v] } + o[('avg_' + v.to_s).to_sym] = values.reduce(:+).to_f / values.size + end] + end + + # Adds relative error to results of solving if some exact method of + # solving was requested. + # + # @param results [Hash] results of solving using requested methods + # @return [Hash] the results with relative error added + def add_relative_error(results) + return results unless @opts[:branch_and_bound] || @opts[:dynamic_programming] + exact_method = @opts[:branch_and_bound] ? :branch_and_bound : :dynamic_programming + results.each_value do |method_results| + method_results.each_value do |res| + res.each_with_index do |r, i| + r[:relative_error] = relative_error(method_results[exact_method][i][:price], r[:price]) + end + end + end + results + end + + # Measure execution time of provided block so that measured time is non-zero. + # + # @yieldparam block for which execution time will be measured + # @return [Hash] solving results with cpu time and wall clock time of execution + def execution_time + exec_count = 1 + result = nil + cpu_time = wall_clock_time = 0.0 + while cpu_time.zero? || wall_clock_time.zero? + b = Benchmark.measure { exec_count.times { result = yield } } + cpu_time += b.total + wall_clock_time += b.real + exec_count *= 2 + end + result.merge(cpu_time: cpu_time, wall_clock_time: wall_clock_time) + end + + # Computes relative error of approximate solution. + # + # @param opt [Numeric] Optimal price. + # @param apx [Numeric] Approximate price. + # @return [Float] Relative error. + def relative_error(opt, apx) + (opt.to_f - apx.to_f) / opt.to_f + end + end +end diff --git a/lib/knapsack_solver/solving_methods/branch_and_bound.rb b/lib/knapsack_solver/solving_methods/branch_and_bound.rb new file mode 100644 index 0000000..64d7092 --- /dev/null +++ b/lib/knapsack_solver/solving_methods/branch_and_bound.rb @@ -0,0 +1,111 @@ +module KnapsackSolver + # This class implements methods for solving 0/1 knapsack problem using + # Branch and Bound method. + class BranchAndBound + # Initializes instance of Brand and Bound 0/1 knapsack problem solver. + # + # @param instance [Instance] 0/1 knapsack problem instance + def initialize(instance) + @instance = instance + @config = Array.new(instance.things.size) + end + + # Solve the instance of 0/1 knapsack problem. + # + # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there) + def run + solve(0) + { price: @best_price, config: @best_config } + end + + protected + + # Solve the problem starting at specified thing. + # + # @param index [Integer] index of thing which will be decided (put in or out from the knapsack) the next + def solve(index) + @config[index] = 0 + solve(index + 1) unless stop(index) + @config[index] = 1 + solve(index + 1) unless stop(index) + end + + # Determine if solving of current branch should continue. + # + # @param index [Integer] index of the last decided thing so far + # @return [true, false] weather to continue with solving current branch. + def stop(index) + # Update of the best price so far + weight = config_weight(0, index) + price = config_price(0, index) + update_best_price(price, weight, index) + # No more things to put into the knapsack + return true if index >= (@instance.things.size - 1) + # The knapsack is overloaded, do not continue this branch + return true if weight > @instance.weight_capacity + if instance_variable_defined?('@best_price') && + ((price + get_price_of_remaining_things(index + 1)) <= @best_price) + # Adding all the ramining things does not produce better price + return true + end + false + end + + # Update the best price achieved so far. + # + # @param price [Integer] price of the current configuration + # @param weight [Integer] weight of the current configuration + # @param index [Integer] index of the next thing presence of which will be decided + def update_best_price(price, weight, index) + if !instance_variable_defined?('@best_price') || + ((weight <= @instance.weight_capacity) && (price > @best_price)) + @best_price = price + valid_len = index + 1 + remaining = @config.size - index - 1 + # All undecided things will not be put into the knapsack + @best_config = @config.slice(0, valid_len).fill(0, valid_len, remaining) + @best_config_index = index + end + end + + # Gets weight of set of things. The set is subset of the things ordered by + # their index. + # + # @param start_index [Integer] index of the first thing included in the set + # @param end_index [Integer] index of the last thing included in the set + # @return [Integer] weight of the things + def config_weight(start_index, end_index) + weight = 0 + @config[start_index..end_index].each_with_index do |presence, index| + weight += presence * @instance.things[index].weight + end + weight + end + + # Gets price of set of things. The set is subset of the things ordered by + # their index. + # + # @param start_index [Integer] index of the first thing included in the set + # @param end_index [Integer] index of the last thing included in the set + # @return [Integer] price of the things + def config_price(start_index, end_index) + price = 0 + @config[start_index..end_index].each_with_index do |presence, index| + price += presence * @instance.things[index].price + end + price + end + + # Gets sum of prices of things for which their presence in the knapsack + # was not decided yet. + # + # @param from_index [Integer] index of the first undecided thing + # @return [Integer] price of the remaining things + def get_price_of_remaining_things(from_index) + price = 0 + to_index = @instance.things.size - 1 + @instance.things[from_index..to_index].each { |t| price += t.price } + price + end + end +end diff --git a/lib/knapsack_solver/solving_methods/dynamic_programming.rb b/lib/knapsack_solver/solving_methods/dynamic_programming.rb new file mode 100644 index 0000000..756a9a6 --- /dev/null +++ b/lib/knapsack_solver/solving_methods/dynamic_programming.rb @@ -0,0 +1,116 @@ +module KnapsackSolver + # This class implements methods for solving 0/1 knapsack problem using + # dynamic programming with decomposition by price. + class DynamicProgramming + # Initializes instance of 0/1 knapsack problem solver based on dynamic + # programming with decomposition by price. + # + # @param instance [Instance] 0/1 knapsack problem instance + def initialize(instance) + @instance = instance + @config = Array.new(instance.things.size) + end + + # Solve the instance of 0/1 knapsack problem. + # + # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there) + def run + solve + { price: @best_price, config: @best_config } + end + + protected + + # Solve the instance of 0/1 knapsack problem using dynamic programming. + def solve + # Dynamic programming table + c = all_things_price + 1 # height of array from 0 to max. price + n = @instance.things.size + 1 # width of array, from 0th thing to Nth + # Value used as infinity in the dynamic programming table + @infinity = (all_things_weight + 1).freeze + @weight_array = Array.new(n) { Array.new(c, @infinity) } + @weight_array[0][0] = 0 + fill_table + find_best_price + configuration_vector + end + + # Fill the dynamic programming table. + def fill_table + (1..@instance.things.size).each do |ni| + (0..all_things_price).each do |ci| + @weight_array[ni][ci] = minimum_weight(ni, ci) + end + end + end + + # Find the value of cell in dynamic programming table. + # + # @param ni [Integer] X axis coordinate + # @param ci [Integer] Y axis coordinate + # @return [Integer] + def minimum_weight(ni, ci) + b = weight_of(ni - 1, ci - @instance.things[ni - 1].price) + b += @instance.things[ni - 1].weight + [weight_of(ni - 1, ci), b].min + end + + # Find the best price from the filled dynamic programming table. + def find_best_price + @best_price = @weight_array.last[0] + (1..all_things_price).each do |i| + @best_price = i if @weight_array.last[i] <= @instance.weight_capacity + end + end + + # Reconstructs configuration vector from dynamic programming table. + def configuration_vector + @best_config = [] + ci = @best_price + @instance.things.size.downto(1) do |i| + ci = determine_config_variable(i, ci) + end + end + + # Determine value of one scalar for the configuration vector. + # + # return [Integer] next Y index to the dynamic programming table + def determine_config_variable(i, ci) + if @weight_array[i][ci] == @weight_array[i - 1][ci] + @best_config[i - 1] = 0 + else + @best_config[i - 1] = 1 + ci -= @instance.things[i - 1].price + end + ci + end + + # Gets weight from dynamic programming table. + # + # @param i [Integer] Y index of dynamic programming table + # @param c [Integer] X index of dynamic programming table + # @return [Integer] the value from the array + def weight_of(i, c) + return @infinity if (i < 0) || (c < 0) + @weight_array[i][c] + end + + # Computes total price of all things of the instance. + # + # @return [Integer] total price + def all_things_price + price = 0 + @instance.things.each { |t| price += t.price } + price + end + + # Computes total weight of all things of the instance. + # + # @return [Integer] total weight + def all_things_weight + weight = 0 + @instance.things.each { |t| weight += t.weight } + weight + end + end +end diff --git a/lib/knapsack_solver/solving_methods/fptas.rb b/lib/knapsack_solver/solving_methods/fptas.rb new file mode 100644 index 0000000..55ee52f --- /dev/null +++ b/lib/knapsack_solver/solving_methods/fptas.rb @@ -0,0 +1,47 @@ +require 'knapsack_solver/solving_methods/dynamic_programming' + +module KnapsackSolver + # This class implements methods for solving 0/1 knapsack problem using Fully + # Polynomial Time Approximation Scheme. + class Fptas + # Initializes 0/1 knapsack FPTAS solver. + # + # @param instance [Instance] Instance of a 0/1 knapsack problem. + # @param epsilon [Instances] Maximum allowed relative error of the resulting price. + def initialize(instance, epsilon) + @instance = instance + @epsilon = epsilon.to_f + @orig_prices = @instance.things.map(&:price) + end + + # Solve the instance of 0/1 knapsack problem using FPTAS. + # + # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there) + def run + modify_prices_for_epsilon! + r = DynamicProgramming.new(@instance).run + p = get_normal_price_from_fptas(r[:config]) + { price: p, config: r[:config] } + end + + protected + + # Modifies prices of the things according to the supplied epsilon constant + # to achieve max. allowed relative error. + def modify_prices_for_epsilon! + m = @instance.things.max_by(&:price).price + k = (@epsilon * m) / @instance.things.size + @instance.things.each { |t| t.price = (t.price.to_f / k).floor } + end + + # Computes resulting price using original unmodified prices of things. + # + # @param presenve [Array] configuration variables vector + # @return [Integer] total price of things in the knapsack + def get_normal_price_from_fptas(presence) + @instance.things.reduce(0) do |price, t| + price + ((presence[t.index] != 0 ? @orig_prices[t.index] : 0)) + end + end + end +end diff --git a/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb b/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb new file mode 100644 index 0000000..8f694fc --- /dev/null +++ b/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb @@ -0,0 +1,56 @@ +module KnapsackSolver + # This class implements methods for solving 0/1 knapsack problem using + # simple heuristic by price to weight ratio. Things with the best price to + # weight ratio are selected first. + class HeuristicPriceToWeight + # Initializes instance of 0/1 knapsack problem solver using simple + # heuristic by price to weight ratio. + # + # @param instance [Instance] 0/1 knapsack problem instance + def initialize(instance) + @instance = instance + @config = Array.new(instance.things.size) { 0 } + @sorted_things = instance.things.sort do |a, b| + (b.price.to_f / b.weight) <=> (a.price.to_f / a.weight) + end + end + + # Solve the instance of 0/1 knapsack problem. + # + # @return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there) + def run + solve + { price: @best_price, config: @best_config } + end + + protected + + # Solve the instance of 0/1 knapsack problem. + def solve + @sorted_things.each do |thing| + break if (config_weight + thing.weight) > @instance.weight_capacity + @config[thing.index] = 1 + end + @best_price = config_price + @best_config = @config.dup + end + + # Gets total weight of things present in the knapsack. + # + # @return [Integer] total weight + def config_weight + @config.each_with_index.reduce(0) do |weight, (presence, index)| + weight + presence * @instance.things[index].weight + end + end + + # Gets total price of things present in the knapsack. + # + # @return [Integer] total price + def config_price + @config.each_with_index.reduce(0) do |price, (presence, index)| + price + presence * @instance.things[index].price + end + end + end +end diff --git a/lib/knapsack_solver/version.rb b/lib/knapsack_solver/version.rb new file mode 100644 index 0000000..3b87713 --- /dev/null +++ b/lib/knapsack_solver/version.rb @@ -0,0 +1,5 @@ +# Namespace for classes and modules for 0/1 knapsack problem utility. +module KnapsackSolver + # Version of this comman-line utility for solving 0/1 knapsack problem. + VERSION = '0.1.0'.freeze +end diff --git a/test/datasets/size_10.dataset b/test/datasets/size_10.dataset new file mode 100644 index 0000000..bcf3857 --- /dev/null +++ b/test/datasets/size_10.dataset @@ -0,0 +1,4 @@ +10 +100 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 100 99 +100 5 225 2 248 8 189 7 221 68 228 6 31 1 91 12 140 21 112 22 118 +100 2 125 1 239 35 223 4 145 7 249 19 78 12 174 3 125 34 221 11 93 diff --git a/test/datasets/size_4.dataset b/test/datasets/size_4.dataset new file mode 100644 index 0000000..0ae0363 --- /dev/null +++ b/test/datasets/size_4.dataset @@ -0,0 +1,4 @@ +4 +100 65 38 20 243 13 107 39 122 +100 21 29 17 190 86 88 52 95 +100 64 155 20 62 52 56 2 170 diff --git a/test/invalid_datasets/invalid_1.dataset b/test/invalid_datasets/invalid_1.dataset new file mode 100644 index 0000000..e69de29 diff --git a/test/invalid_datasets/invalid_2.dataset b/test/invalid_datasets/invalid_2.dataset new file mode 100644 index 0000000..7b6743e --- /dev/null +++ b/test/invalid_datasets/invalid_2.dataset @@ -0,0 +1,3 @@ +100 65 38 20 243 13 107 39 122 +100 21 29 17 190 86 88 52 95 +100 64 155 20 62 52 56 2 170 diff --git a/test/invalid_datasets/invalid_3.dataset b/test/invalid_datasets/invalid_3.dataset new file mode 100644 index 0000000..f56eb9a --- /dev/null +++ b/test/invalid_datasets/invalid_3.dataset @@ -0,0 +1,4 @@ +-4 +100 65 38 20 243 13 107 39 122 +100 21 29 17 190 86 88 52 95 +100 64 155 20 62 52 56 2 170 diff --git a/test/invalid_datasets/invalid_4.dataset b/test/invalid_datasets/invalid_4.dataset new file mode 100644 index 0000000..f976d55 --- /dev/null +++ b/test/invalid_datasets/invalid_4.dataset @@ -0,0 +1,4 @@ +4.2 +100 65 38 20 243 13 107 39 122 +100 21 29 17 190 86 88 52 95 +100 64 155 20 62 52 56 2 170 diff --git a/test/invalid_datasets/invalid_5.dataset b/test/invalid_datasets/invalid_5.dataset new file mode 100644 index 0000000..733787e --- /dev/null +++ b/test/invalid_datasets/invalid_5.dataset @@ -0,0 +1,2 @@ +4 + diff --git a/test/invalid_datasets/invalid_6.dataset b/test/invalid_datasets/invalid_6.dataset new file mode 100644 index 0000000..3d81f69 --- /dev/null +++ b/test/invalid_datasets/invalid_6.dataset @@ -0,0 +1,2 @@ +4 +100 65 38 20 243 13 107 39 diff --git a/test/invalid_datasets/invalid_7.dataset b/test/invalid_datasets/invalid_7.dataset new file mode 100644 index 0000000..19bc569 --- /dev/null +++ b/test/invalid_datasets/invalid_7.dataset @@ -0,0 +1,4 @@ +4 +100 65 38 20 243 13 107 39 122 +100 21 29 17 190 86 88 52 95 +100 -64 155 20 62 52 56 2 170 diff --git a/test/invalid_datasets/invalid_8.dataset b/test/invalid_datasets/invalid_8.dataset new file mode 100644 index 0000000..3a94b69 --- /dev/null +++ b/test/invalid_datasets/invalid_8.dataset @@ -0,0 +1,4 @@ +4 +100 65 38 20 243 13 107 39 122 +100 21 29 17 190 86 88.888 52 95 +100 64 155 20 62 52 56 2 170 diff --git a/test/knapsack_solver_matchers.rb b/test/knapsack_solver_matchers.rb new file mode 100644 index 0000000..754fb20 --- /dev/null +++ b/test/knapsack_solver_matchers.rb @@ -0,0 +1,103 @@ +require 'rspec/expectations' + +def comment_lines(file_path) + File.open(file_path, 'r').each_line.select { |l| l.chars.first == '#' } +end + +def data_lines(file_path) + File.open(file_path, 'r').each_line.select { |l| l.chars.first != '#' } +end + + +RSpec::Matchers.define :be_a_regular_file do + match do |actual| + File.file?(actual) + end +end + +RSpec::Matchers.define :be_an_empty_directory do + match do |actual| + Dir.empty?(actual) + end +end + +RSpec::Matchers.define :be_a_valid_results_file do + match do |actual| + begin + comment_lines = comment_lines(actual) + data_lines = data_lines(actual) + # It must have 3 lines: 2 comments and >= 1 data line + return false if comment_lines.size != 2 || data_lines.size < 1 + # Data line must consist of non-negative numbers and array 1 and 0 + data_lines.each do |l| + l.scan(/\[[^\]]*\]/).first.tr('[]', '').split(',').map { |n| n.to_i }.each do |i| + return false if i != 0 && i != 1 + end + l.scan(/[0-9\.]+/).map { |n| n.to_f }.each do |i| + return false if i < 0 + end + end + true + rescue + false + end + end +end + +RSpec::Matchers.define :be_a_equal_to_results_file do |good| + match do |actual| + begin + lines = data_lines(actual) + good_lines = data_lines(good) + return false if lines.size != good_lines.size + lines.each_with_index do |l, i| + # Check price and configuration + return false if l.split(']').first != good_lines[i].split(']').first + # Check relative error + return false if l.split().last != good_lines[i].split().last + return false if l.split().size != good_lines[i].split().size + end + true + rescue + false + end + end +end + +RSpec::Matchers.define :be_a_equal_to_stats_file do |good| + match do |actual| + begin + lines = data_lines(actual) + good_lines = data_lines(good) + return false if lines.size != good_lines.size + lines.each_with_index do |l, i| + # Check average price + return false if l.split().first != good_lines[i].split().first + # Check average relative error + return false if l.split().last != good_lines[i].split().last + return false if l.split().size != good_lines[i].split().size + end + true + rescue + false + end + end +end + +RSpec::Matchers.define :be_a_valid_stats_file do + match do |actual| + begin + comment_lines = comment_lines(actual) + data_lines = data_lines(actual) + # It must have 3 lines: 2 comments and 1 data line + return false if comment_lines.size != 2 || data_lines.size != 1 + # Data line must consist of non-negative numbers + data_lines.first.split.map { |i| i.to_f }.each do |n| + return false if n < 0 + end + true + rescue + false + end + end +end diff --git a/test/knapsack_solver_spec.rb b/test/knapsack_solver_spec.rb new file mode 100644 index 0000000..9b825a6 --- /dev/null +++ b/test/knapsack_solver_spec.rb @@ -0,0 +1,261 @@ +require 'rspec' +require 'tmpdir' +require_relative 'spec_helper' +require_relative 'knapsack_solver_matchers' +require_relative '../lib/knapsack_solver/cli.rb' +require_relative '../lib/knapsack_solver/version.rb' + +module FileHelper + def file_list(directory, files) + files.map { |f| File.join(directory, f) } + end +end + +module ArgumentHelper + def args(args_string = nil) + return [] if args_string.nil? + args_string.split + end + + def args_in_dataset_out_file(args_string, tmpdir) + args(args_string) + ['-o', tmpdir, 'test/datasets/size_4.dataset', 'test/datasets/size_10.dataset'] + end +end + +describe KnapsackSolver::CLI do + include FileHelper + include ArgumentHelper + + subject(:cli) { KnapsackSolver::CLI } + + context 'options' do + it 'recognizes invalid options' do + expect { cli.run(args('-a')) }.to raise_error(OptionParser::InvalidOption) + expect { cli.run(args('-k -h')) }.to raise_error(OptionParser::InvalidOption) + expect { cli.run(args('-x -b')) }.to raise_error(OptionParser::InvalidOption) + end + + it 'detects missing arguments' do + expect { cli.run(args('-o')) }.to raise_error(OptionParser::MissingArgument) + expect { cli.run(args('-g')) }.to raise_error(OptionParser::MissingArgument) + end + + it '-h has the top priority among valid options' do + expect { cli.run(args('-b -v -h')) }.to output(/Usage:/).to_stdout + expect { cli.run(args('-b -h -v')) }.to output(/Usage:/).to_stdout + expect { cli.run(args('-h -b -v')) }.to output(/Usage:/).to_stdout + end + + it '-v has a second from the top priority among valid options' do + expect { cli.run(args('-v -h')) }.to output(/Usage:/).to_stdout + expect { cli.run(args('-v -b')) }.to output(/knapsack_solver #{KnapsackSolver::VERSION}/).to_stdout + end + + it 'at least one method of solving must be selected' do + Dir.mktmpdir() do |tmpdir| + expect { cli.run(args()) }.to raise_error(/At least one method of solving must be requested/) + expect { cli.run(args_in_dataset_out_file('-b', tmpdir)) }.not_to raise_error + end + end + + it 'FPTAS must have epsilon constant provided' do + Dir.mktmpdir() do |tmpdir| + expect { cli.run(args_in_dataset_out_file('-f', tmpdir)) }.to raise_error(/Missing FPTAS epsilon constant/) + expect { cli.run(args_in_dataset_out_file('-f -e 0.5', tmpdir)) }.not_to raise_error + end + end + + it 'FPTAS epsilon constant must be number from range (0,1)' do + Dir.mktmpdir() do |tmpdir| + expect { cli.run(args_in_dataset_out_file('-f -e asdf', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/) + expect { cli.run(args_in_dataset_out_file('-f -e 0.5x', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/) + expect { cli.run(args_in_dataset_out_file('-f -e -0.3', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/) + expect { cli.run(args_in_dataset_out_file('-f -e 0', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/) + expect { cli.run(args_in_dataset_out_file('-f -e 0.01', tmpdir)) }.not_to raise_error + expect { cli.run(args_in_dataset_out_file('-f -e 0.99', tmpdir)) }.not_to raise_error + expect { cli.run(args_in_dataset_out_file('-f -e 1', tmpdir)) }.to raise_error(/FPTAS epsilon must be number from range \(0,1\)/) + end + end + + it 'epsilon constant must not be provided when FPTAS is not selected' do + Dir.mktmpdir() do |tmpdir| + expect { cli.run(args_in_dataset_out_file('-b -e 0.5', tmpdir)) }.to raise_error(/epsilon constant must not be provided when FPTAS is not selected/) + expect { cli.run(args_in_dataset_out_file('-b -f -e 0.5', tmpdir)) }.not_to raise_error + end + end + + end + + context 'positional arguments' do + it 'must have at least one dataset provided' do + expect { cli.run(args('-b')) }.to raise_error(/Missing datset file\(s\)/) + end + + it 'dataset path must be a path to a regular file' do + Dir.mktmpdir do |tmpdir| + expect { cli.run(args('-b ' + tmpdir)) }.to raise_error(/is not a regular file/) + end + end + + it 'dataset file must exist' do + Dir.mktmpdir do |tmpdir| + not_existent_file = File.join(tmpdir, 'size_4.dataset') + expect { cli.run(args('-b ' + not_existent_file)) }.to raise_error(/does not exists/) + end + end + + it 'dataset file must be readable' do + Dir.mktmpdir do |tmpdir| + FileUtils.cp('test/datasets/size_4.dataset', tmpdir) + not_readable_file = File.join(tmpdir, 'size_4.dataset') + FileUtils.chmod('a-r', not_readable_file) + expect { cli.run(args('-b ' + not_readable_file)) }.to raise_error(/is not readable/) + end + end + + it 'dataset file must have correct format' do + Dir.mktmpdir do |tmpdir| + invalid_files = %w(invalid_1.dataset + invalid_2.dataset + invalid_3.dataset + invalid_4.dataset + invalid_5.dataset + invalid_6.dataset + invalid_7.dataset + invalid_8.dataset) + error_messages = ['missing ID', + 'first line does not contain ID', + 'ID is negative', + 'ID is not an integer', + 'missing knapsack capacity', + 'missing pairs \(price, weight\)', + 'instance desctiption contains negative number', + 'instance desctiption does not contain only integers'] + file_list('test/invalid_datasets', invalid_files).each_with_index do |f, i| + expect { cli.run(args('-d ' + f)) }.to raise_error(/#{error_messages[i]}/) + end + end + end + end + + context 'output of results' do + it 'directory for the output logs must exist' do + Dir.mktmpdir do |tmpdir| + not_existent_file = File.join(tmpdir, 'size_4.dataset') + expect { cli.run(args('-b -o ' + not_existent_file)) }.to raise_error(/does not exists/) + end + end + + it 'path to a directory for the output logs must point to a directory' do + Dir.mktmpdir do |tmpdir| + FileUtils.cp('test/datasets/size_4.dataset', tmpdir) + file = File.join(tmpdir, 'size_4.dataset') + expect { cli.run(args('-b -o ' + file)) }.to raise_error(/is not a directory/) + end + end + + it 'directory for the output logs must be writable' do + Dir.mktmpdir do |tmpdir| + not_writable_dir = File.join(tmpdir, 'dir') + Dir.mkdir(not_writable_dir) + FileUtils.chmod('a-w', not_writable_dir) + expect { cli.run(args('-b -o ' + not_writable_dir)) }.to raise_error(/is not writable/) + end + end + + it 'directory for the graph files must exist' do + Dir.mktmpdir do |tmpdir| + not_existent_file = File.join(tmpdir, 'size_4.dataset') + expect { cli.run(args('-b -g ' + not_existent_file)) }.to raise_error(/does not exists/) + end + end + + it 'path to a directory for the graph files must point to a directory' do + Dir.mktmpdir do |tmpdir| + FileUtils.cp('test/datasets/size_4.dataset', tmpdir) + file = File.join(tmpdir, 'size_4.dataset') + expect { cli.run(args('-b -g ' + file)) }.to raise_error(/is not a directory/) + end + end + + it 'directory for the graph files must be writable' do + Dir.mktmpdir do |tmpdir| + not_writable_dir = File.join(tmpdir, 'dir') + Dir.mkdir(not_writable_dir) + FileUtils.chmod('a-w', not_writable_dir) + expect { cli.run(args('-b -g ' + not_writable_dir)) }.to raise_error(/is not writable/) + end + end + + it 'writes graph files' do + Dir.mktmpdir do |tmpdir| + png_files = %w(avg_price.png avg_cpu_time.png avg_wall_clock_time.png avg_relative_error.png) + gnuplot_files = %w(avg_price.gnuplot avg_cpu_time.gnuplot avg_wall_clock_time.gnuplot avg_relative_error.gnuplot) + files = png_files + gnuplot_files + cli.run(args_in_dataset_out_file('-b -g ' + tmpdir, tmpdir)) + expect(file_list(tmpdir, files)).to all be_a_regular_file + end + end + + it 'writes results and stats to files' do + Dir.mktmpdir do |tmpdir| + results_files = %w(size_4_branch_and_bound.results size_10_branch_and_bound.results) + stats_files = %w(size_4_branch_and_bound.stats size_10_branch_and_bound.stats) + files = results_files + stats_files + cli.run(args_in_dataset_out_file('-b', tmpdir)) + expect(file_list(tmpdir, files)).to all be_a_regular_file + end + end + + it 'writes results and stats to stdout' do + results_files = %w(size_4_branch_and_bound.results size_10_branch_and_bound.results) + stats_files = %w(size_4_branch_and_bound.stats size_10_branch_and_bound.stats) + files = results_files + stats_files + files.each do |f| + expect { cli.run(args('-b test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.to output(/#{f}/).to_stdout + end + end + + it 'adds relative error if an exact solving method is selected' do + expect { cli.run(args('-r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.not_to output(/avg_relative_error/).to_stdout + expect { cli.run(args('-f -e 0.5 -r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.not_to output(/avg_relative_error/).to_stdout + expect { cli.run(args('-b -r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.to output(/avg_relative_error/).to_stdout + expect { cli.run(args('-d -r test/datasets/size_4.dataset test/datasets/size_10.dataset')) }.to output(/avg_relative_error/).to_stdout + end + + it 'produces correct results' do + Dir.mktmpdir do |tmpdir| + results_files = %w(size_10_dynamic_programming.results + size_10_fptas.results + size_10_heuristic.results + size_4_dynamic_programming.results + size_4_fptas.results + size_4_heuristic.results) + stats_files = %w(size_10_dynamic_programming.stats + size_10_fptas.stats + size_10_heuristic.stats + size_4_dynamic_programming.stats + size_4_fptas.stats + size_4_heuristic.stats) + good_results_files = results_files.map { |f| File.join('test/output_logs', f) } + good_stats_files = stats_files.map { |f| File.join('test/output_logs', f) } + files = results_files + stats_files + cli.run(args_in_dataset_out_file('-b -d -r -f -e 0.5', tmpdir)) + expect(file_list(tmpdir, files)).to all be_a_regular_file + expect(file_list(tmpdir, results_files)).to all be_a_valid_results_file + expect(file_list(tmpdir, stats_files)).to all be_a_valid_stats_file + + file_list(tmpdir, results_files).each_with_index do |f, i| + expect(f).to be_a_equal_to_results_file(good_results_files[i]) + end + + file_list(tmpdir, stats_files).each_with_index do |f, i| + expect(f).to be_a_equal_to_stats_file(good_stats_files[i]) + end + end + + end + + end + +end diff --git a/test/output_logs/size_10_dynamic_programming.results b/test/output_logs/size_10_dynamic_programming.results new file mode 100644 index 0000000..62c8189 --- /dev/null +++ b/test/output_logs/size_10_dynamic_programming.results @@ -0,0 +1,5 @@ +# ../test/output_logs/size_10_dynamic_programming.results +# price config cpu_time wall_clock_time relative_error +100 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 0.009999999999999981 0.016795745003037155 0.0 +6 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.005632286978652701 0.0 +19 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.011052408022806048 0.0 diff --git a/test/output_logs/size_10_dynamic_programming.stats b/test/output_logs/size_10_dynamic_programming.stats new file mode 100644 index 0000000..7ec5c52 --- /dev/null +++ b/test/output_logs/size_10_dynamic_programming.stats @@ -0,0 +1,3 @@ +# ../test/output_logs/size_10_dynamic_programming.stats +# avg_price avg_cpu_time avg_wall_clock_time avg_relative_error +41.666666666666664 0.01 0.011160146668165302 0.0 diff --git a/test/output_logs/size_10_fptas.results b/test/output_logs/size_10_fptas.results new file mode 100644 index 0000000..154def2 --- /dev/null +++ b/test/output_logs/size_10_fptas.results @@ -0,0 +1,5 @@ +# ../test/output_logs/size_10_fptas.results +# price config cpu_time wall_clock_time relative_error +100 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 0.009999999999999981 0.003663021983811632 0.0 +6 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.008500695985276252 0.0 +19 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.013226451963419095 0.0 diff --git a/test/output_logs/size_10_fptas.stats b/test/output_logs/size_10_fptas.stats new file mode 100644 index 0000000..fdfe485 --- /dev/null +++ b/test/output_logs/size_10_fptas.stats @@ -0,0 +1,3 @@ +# ../test/output_logs/size_10_fptas.stats +# avg_price avg_cpu_time avg_wall_clock_time avg_relative_error +41.666666666666664 0.01 0.008463389977502326 0.0 diff --git a/test/output_logs/size_10_heuristic.results b/test/output_logs/size_10_heuristic.results new file mode 100644 index 0000000..7b0058c --- /dev/null +++ b/test/output_logs/size_10_heuristic.results @@ -0,0 +1,5 @@ +# ../test/output_logs/size_10_heuristic.results +# price config cpu_time wall_clock_time relative_error +100 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 0.009999999999999981 0.010833156033186242 0.0 +0 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 0.010000000000000009 0.005375430977437645 1.0 +19 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] 0.010000000000000009 0.02155825894442387 0.0 diff --git a/test/output_logs/size_10_heuristic.stats b/test/output_logs/size_10_heuristic.stats new file mode 100644 index 0000000..212314f --- /dev/null +++ b/test/output_logs/size_10_heuristic.stats @@ -0,0 +1,3 @@ +# ../test/output_logs/size_10_heuristic.stats +# avg_price avg_cpu_time avg_wall_clock_time avg_relative_error +39.666666666666664 0.01 0.012588948651682585 0.3333333333333333 diff --git a/test/output_logs/size_4_dynamic_programming.results b/test/output_logs/size_4_dynamic_programming.results new file mode 100644 index 0000000..915cf14 --- /dev/null +++ b/test/output_logs/size_4_dynamic_programming.results @@ -0,0 +1,5 @@ +# ../test/output_logs/size_4_dynamic_programming.results +# price config cpu_time wall_clock_time relative_error +65 [1, 0, 0, 0] 0.009999999999999995 0.011663347017019987 0.0 +86 [0, 0, 1, 0] 0.010000000000000009 0.006198941962793469 0.0 +52 [0, 0, 1, 0] 0.009999999999999995 0.012558827002067119 0.0 diff --git a/test/output_logs/size_4_dynamic_programming.stats b/test/output_logs/size_4_dynamic_programming.stats new file mode 100644 index 0000000..fb64352 --- /dev/null +++ b/test/output_logs/size_4_dynamic_programming.stats @@ -0,0 +1,3 @@ +# ../test/output_logs/size_4_dynamic_programming.stats +# avg_price avg_cpu_time avg_wall_clock_time avg_relative_error +67.66666666666667 0.01 0.010140371993960192 0.0 diff --git a/test/output_logs/size_4_fptas.results b/test/output_logs/size_4_fptas.results new file mode 100644 index 0000000..e86ea0d --- /dev/null +++ b/test/output_logs/size_4_fptas.results @@ -0,0 +1,5 @@ +# ../test/output_logs/size_4_fptas.results +# price config cpu_time wall_clock_time relative_error +65 [1, 0, 0, 0] 0.009999999999999981 0.006782401964301243 0.0 +86 [0, 0, 1, 0] 0.010000000000000009 0.012463745952118188 0.0 +52 [0, 0, 1, 0] 0.010000000000000009 0.006875811057398096 0.0 diff --git a/test/output_logs/size_4_fptas.stats b/test/output_logs/size_4_fptas.stats new file mode 100644 index 0000000..185ff93 --- /dev/null +++ b/test/output_logs/size_4_fptas.stats @@ -0,0 +1,3 @@ +# ../test/output_logs/size_4_fptas.stats +# avg_price avg_cpu_time avg_wall_clock_time avg_relative_error +67.66666666666667 0.01 0.008707319657939175 0.0 diff --git a/test/output_logs/size_4_heuristic.results b/test/output_logs/size_4_heuristic.results new file mode 100644 index 0000000..67825c4 --- /dev/null +++ b/test/output_logs/size_4_heuristic.results @@ -0,0 +1,5 @@ +# ../test/output_logs/size_4_heuristic.results +# price config cpu_time wall_clock_time relative_error +65 [1, 0, 0, 0] 0.009999999999999995 0.0105733550444711 0.0 +86 [0, 0, 1, 0] 0.010000000000000009 0.00713886899757199 0.0 +52 [0, 0, 1, 0] 0.010000000000000009 0.014065870986087248 0.0 diff --git a/test/output_logs/size_4_heuristic.stats b/test/output_logs/size_4_heuristic.stats new file mode 100644 index 0000000..889433d --- /dev/null +++ b/test/output_logs/size_4_heuristic.stats @@ -0,0 +1,3 @@ +# ../test/output_logs/size_4_heuristic.stats +# avg_price avg_cpu_time avg_wall_clock_time avg_relative_error +67.66666666666667 0.010000000000000004 0.010592698342710113 0.0 diff --git a/test/spec_helper.rb b/test/spec_helper.rb new file mode 100644 index 0000000..adec803 --- /dev/null +++ b/test/spec_helper.rb @@ -0,0 +1,5 @@ +RSpec.configure do |c| + c.color = true + c.formatter = :documentation + c.tty = true +end -- cgit v1.2.3