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:
- 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:
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
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:
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:
Create your gtest::Test
class and set up initial conditions in the SetUp()
method.
Certainly! If you want to verify that the solution meets expectations, it's useful to implement a function like this:
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.