Tests

The Importance of Testing in Software Development

In modern software development, testing is a fundamental practice that ensures the reliability, stability, and quality of code. Implementing thorough and automated testing provides numerous benefits, making it an indispensable part of the development process. Here are some key reasons why testing is crucial in desition diagram:

1. Complexity of Algorithms

The algorithms involved in creating and manipulating decision diagrams are complex and can be prone to subtle bugs. Automated testing ensures that these algorithms work correctly and consistently, which is vital for producing accurate results.

2. State Management

The ProblemKnapsack class handles various states and transitions, which can be intricate. Tests verify that the state management logic is implemented correctly, ensuring that transitions between states occur as expected and that the resulting states are valid.

3. Decision Diagram Integrity

Decision diagrams are central to this program. Tests confirm that the diagrams are constructed and reduced properly, maintaining their integrity and representing the problem accurately. This is critical for the correctness of the algorithm and the validity of the results.

4. Validation of Results

The program aims to solve optimization problems, so the accuracy of the results is paramount. Tests verify that the program produces the correct solutions for given inputs, ensuring the reliability of the results and building confidence in the program's capabilities.

Implementation in Our Program

The program implemented in this tutorial provides a framework for solving the problem using decision diagrams. To ensure the correctness and reliability of our solution, we have the posibility to integrate a series of tests using differents Python's or C++'s frameworks. These tests are designed to verify various aspects of the implementation, including:

• Correct initialization and state management of the problem class.
• Proper functioning of the decision diagram creation process.
• Verification of the algorithm's output against expected results.
• Ensuring the integrity of graph representations and their properties.

By incorporating these tests, we can confidently develop and extend our solution, knowing that each component is thoroughly validated and performs as intended.

Tutorial: Implementing a Knapsack Problem with Decision Diagrams

Introduction

In this tutorial, we will walk through the implementation of a Knapsack problem using decision diagrams. The Knapsack problem is a classic optimization problem where the goal is to maximize the total value of items placed in a knapsack without exceeding its capacity. We will leverage decision diagrams to efficiently solve this problem.

Prerequisites

Before you start, make sure you have the following installed:

pythonC++

• Python 3.x
• The unittest package (included in the Python standard library)
• The unittest.mock package (included in the Python standard library)
• Basic knowledge of Python and object-oriented programming

• C++ > 17
• Cmake 3.27
• Google Test (gtest) framework
• Basic knowledge of C++ and object-oriented programming

Project Structure

Here is the project structure we'll be working with:

├── Class/
│   ├── Problems/
│   │   └── AbstractProblemClass.py
│   ├── DD.py
│   ├── ObjectiveFunction/
│   │   ├── ObjectiveFunction.py
│   │   └── LinearObjectiveDP.py
├── Test/
│   ├── init.py
│   ├── test_knapsack.py
│   ├── gml_files/
│   ├── dd_controlled_generators/
│   └── txt_files/
└── main.py

Step-by-Step Implementation

1. Define the Knapsack Problem

Create a class that inherits from AbstractProblem and define the ProblemKnapsack class:

pythonC++

from Class.Problems.AbstractProblemClass import AbstractProblemclass

ProblemKnapsack(AbstractProblem):
    def init(self, initial_state, variables, matrix_of_weight, right_side_of_restrictions):
            super().init(initial_state, variables)
        self.matrix_of_weight = matrix_of_weight
        self.right_side_of_restrictions = right_side_of_restrictions

def equals(self, state_one, state_two):
        return state_one == state_two

def transition_function(self, previus_state, variable_id, variable_value):
        new_state = [int(previus_state)+matrix_of_weigth[int(variable_id[2:])-1]*int(variable_value)]
        isFeasible = int(state) <= self.right_side_of_restrictions
        return new_state, isFeasible

def get_priority_for_discard_node(self, state):
        return state

def get_priority_for_merge_nodes(self, id, state):
        return -int(id)

def merge_operator(self, state_one, state_two):
        return max(state_one, state_two)

def get_state_as_string(self, state):
        return str(state)

#include "AbstractProblemClass.h"
#include`<iostream>`
#include `<string>`
#include `<vector>`
#include `<algorithm>`
#include `<map>`
#include `<cassert>`
#include `<set>`
using namespace std;
KnapsackProblem::KnapsackProblem(vector `<int>` &initial_state, const vector<pair<string, vector `<int>`>>& variables,
                                vector<vector `<int>`> matrix_of_weight, vector `<int>` right_side_of_restrictions)
        : AbstractProblem(initial_state, variables),
        matrix_of_weight(matrix_of_weight),
        right_side_of_restrictions(right_side_of_restrictions)
{

}
bool KnapsackProblem::equals(const vector`<int>`& state_one, const vector `<int>`& state_two) const {
    return state_one == state_two;
}

pair<vector`<int>`, bool> KnapsackProblem::transition_function(const vector `<int>`& previous_state, const string& variable_id, int variable_value) const {
    bool isFeasible = true;
    vector `<int>` state = {};

for (size_t row = 0; row < matrix_of_wheight.size(); ++row) {
        const vector`<int>`& row_of_matrix = matrix_of_wheight[row];
        int new_state = previous_state[row] + row_of_matrix[stoi(variable_id.substr(2)) - 1] * variable_value;
        state.push_back(new_state);
        state.push_back(new_state);
        bool isFeasible_this_row = state[row] <= right_side_of_restrictions[row];
        isFeasible = isFeasible && isFeasible_this_row;
    }

return make_pair(state, isFeasible);
}

int KnapsackProblem::get_priority_for_discard_node(const vector`<int>`& state) const {
    int total = 0;
    for (int i : state) {
        total += i;
    }
    return -total;
}

int KnapsackProblem::get_priority_for_merge_nodes(const int node_id, const vector`<int>`& state) const {
    return -node_id;
}

vector`<int>` KnapsackProblem::merge_operator(const vector `<int>`& state_one, const vector `<int>`& state_two) const {
    vector `<int>` state;
    state.push_back(state_one[0]);
    state.push_back(state_two.back());
    sort(state.begin(), state.end());
    return state;
}

string KnapsackProblem::get_state_as_string(const vector`<int>`& state) const {
    string result = "[";
    for (int i = 0; i < state.size(); ++i) {
        result += to_string(state[i]);
        if (i != state.size() - 1) {
            result += ", ";
        }
    }
    result += "]";
    return result;
}

2. Implement Unit Tests

Create unit tests to ensure the correctness of the implementation:

2.1 Import Necessary Modules and Classes:

First, ensure you have imported all necessary modules and classes required for testing. This includes unittest, unittest.mock, and the classes related to your knapsack problem

pythonC++

import unittest

from unittest.mock import patch
from Class.Problems.AbstractProblemClass import AbstractProblem
from Class.DD import DD
from Class.ObjectiveFunction.ObjectiveFunction import ObjectiveFunction, LinearObjectiveDP
from contextlib import contextmanager

import dd_controlled_generators.DDKnapsack as DDKnapsack
import dd_controlled_generators.ReduceDDKnapsack as ReduceDDKnapsack
import dd_controlled_generators.RestrictedDDKnapsack as RestrictedDDKnapsack
import dd_controlled_generators.FalseDDKnapsack as FalseDDKnapsack
import dd_controlled_generators.RelaxedDDKnapsack as RelaxedDDKnapsack

import io

#include <gtest/gtest.h>
#include "../../Examples/KnapsackState/KnapsackProblemState.h"
#include "../../Class/DD.h"
#include "../../Class/ObjectiveFunction/LinearObjectiveDP.h"
#include "../../Class/ObjectiveFunction/ObjectiveFunction.h"
#include "dd_controller_generators/DDKnapsackState.cpp"

#include`<iostream>`
#include `<string>`
#include `<vector>`
#include `<algorithm>`
#include `<map>`
#include `<memory>`
#include `<filesystem>`

2.2 Create a Context Manager for Assertions:

Define a context manager to handle assertions without raising exceptions.

@contextmanager
defassertNoRaise():
   try:
    yield
   exceptExceptionas e:
    raiseAssertionError(f"Se generó una excepción: {e}")

Warning

This function is just recomended in python.

2.3 Define the Test Class and Set Up Initial Conditions:

pythonC++

Create your unittest.TestCase class and set up initial conditions in the setUp() method.

class ProblemKnapsackTest(unittest.TestCase):

def setUp(self):
        knapsack_initial_state = [0]
        knapsack_variables = [('x_1', [0, 1]), ('x_2', [0, 1]), ('x_3', [0, 1]), ('x_4', [0, 1])]
        self.knapsack_instance = ProblemKnapsack(initial_state=knapsack_initial_state, variables=knapsack_variables)
        self.dd_knapsack_instance = DD(self.knapsack_instance)
        self.dd_knapsack_instance.create_decision_diagram(False)

Create your gtest::Test class and set up initial conditions in the SetUp() method.

class ProblemKnapsackTestState : public ::testing::Test {
protected:
    void SetUp() override {
        initial_state = new State({0, 0});
        vector<pair<string, vector`<int>`>> variables = {
                make_pair("x_1", vector `<int>`{0, 1}),
                make_pair("x_2", vector `<int>`{0, 1}),
                make_pair("x_3", vector `<int>`{0, 1}),
                make_pair("x_4", vector `<int>`{0, 1})
        };
        vector<vector `<int>`> matrix_of_wheight = {{3, 3, 4, 6}};
        vector `<int>` right_side_of_restrictions = {6};
        knapsack_instance = new KnapsackProblemState(*initial_state, variables, matrix_of_wheight, right_side_of_restrictions);
        dd_instance = new DD(*knapsack_instance);
        dd_instance->create_decision_diagram(false);
        source_directory = fs::current_path().parent_path().string();
    }
    void TearDown() override {
        delete knapsack_instance;
        delete dd_instance;
        delete initial_state;}
    State* initial_state;
    KnapsackProblemState* knapsack_instance;
    DD `<State>`* dd_instance;
    string source_directory;
};

2.5 Implement Test Methods:

Implement various test methods to validate different aspects of your knapsack problem implementation. Here are some examples:

If you want to verify that the structure of the diagram meets your requirements, you can implement a function like this:

pythonC++

def test_create_reduce_dd_graph_equal(self):
    self.dd_knapsack_instance.create_reduce_decision_diagram(verbose=False)
    resultado =self.dd_knapsack_instance.get_decision_diagram_graph() == ReduceDDKnapsack.graph
    self.assertTrue(resultado)

Create your gtest::Test class and set up initial conditions in the SetUp() method.

TEST_F(ProblemKnapsackTestState, TestCreateReduceDDGraphEqual) {
    Graph expected_graph = GetReduceDDKnapsackState();
    dd_instance->create_reduce_decision_diagram();

ASSERT_TRUE(dd_instance->get_decision_diagram() == expected_graph);
}

Certainly! If you want to verify that the solution meets expectations, it's useful to implement a function like this:

pythonC++

def test_get_solution_for_DD(self):
    weigths = [-5, 1, 18, 17]
    value, path =self.get_value_path_solution(weigths)
    expected_value = 18
    expected_path =' arc_0_1(0)-> arc_1_3(0)-> arc_3_7(1)-> arc_7_10(0)'

self.assertEqual(value, expected_value)
    self.assertEqual(path, expected_path)

def get_value_path_solution(self, weigths):
    objective_function_instance = ObjectiveFunction(self.dd_knapsack_instance)
    linear_objective_instance = LinearObjectiveDP(weigths, 'max')
    objective_function_instance.set_objective(linear_objective_instance)
    answer = objective_function_instance.solve_dd()
    return answer.value, answer.path

ObjectiveStruct`<State>` getLinearDpSolution() {
    vector `<int>` objective_weights = {-5, 1, 18, 17};
    ObjectiveFunction objective_function_instance = ObjectiveFunction `<State>`(*dd_instance);
    LinearObjectiveDP linear_objective_instance = LinearObjectiveDP `<State>`(objective_weights, "max");
    objective_function_instance.set_objective_function(linear_objective_instance);

return objective_function_instance.solve_dd();
}

TEST_F(ProblemKnapsackTestState, GetSolutionForDD) {
    ObjectiveStruct solution = getLinearDpSolution();
    int expected_value = 18;
    string expected_path = " arc_0_1(0)-> arc_1_3(0)-> arc_3_7(1)-> arc_7_10(0)";
    ASSERT_EQ(solution.value, expected_value);
    ASSERT_EQ(solution.path, expected_path);
}

2.6 Run the Tests

Run the test suite to ensure all tests pass successfully.

pythonC++

if__name__ == '__main__':
    unittest.main()

int main(int argc, char **argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}