Testing

The Importance of Testing in Software Development

Testing is a fundamental practice that ensures code reliability, stability, and quality in modern software development. 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 decision diagrams:

1. Algorithm complexity

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

2. State management

Classes such as the KnapsackProblem class handle 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 the DD suite. Tests confirm that the diagrams are constructed and reduced correctly, maintaining their integrity and representing the problem accurately. These tests are critical for the algorithm's correctness and the results' validity.

4. Results validation

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

Implementation in DD-Suite

DD-suite provides a framework for solving optimization problems using decision diagrams. To ensure the correctness and reliability of our solution, we integrate a series of tests using different 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.
• Verify 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 validated and performs as intended.

Tutorial: Implementing test for the knapsack problem

Introduction

This tutorial will walk through implementing a knapsack problem and its tests using DDs.

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:

PythonC++

├── SourceCode/
│   ├── GraphAlgorithms/
│   │   ├── ShortestLongestPath/
│   │   │   ├── PathStructure.py
│   │   │   └── ShortestLongestPath.py
│   ├── Problems/
│   │   └── AbstractProblemClass.py
│   ├── DD.py
├── Test/
│   ├── init.py
│   ├── test_knapsack.py
│   ├── gml_files/
│   ├── dd_controlled_generators/
│   └── txt_files/
└── main.py

├── SourceCode/
│   ├── GraphAlgorithms/
│   │   ├── ShortestLongestPath/
│   │   │   ├── PathStructure.h
│   │   │   ├── PathStructure.cpp
│   │   │   ├── ShortestLongestPath.h
│   │   │   └── ShortestLongestPath.cpp
│   ├── Problems/
│   │   ├── AbstractProblemClass.h
│   │   └── AbstractProblemClass.cpp
│   ├── DD.h
│   ├── DD.cpp
├── Test/
│   ├── test_knapsack.cpp
│   ├── gml_files/
│   ├── dd_controlled_generators/
│   └── txt_files/
└── main.cpp

Step-by-step implementation of unit tests

First, make sure you have created a KnapsackProblem class that inherits from AbstractProblem. See Problem implementation for a step-by-step tutorial on how to do so. We then create the following unit tests to ensure the implementation is correct.

1. Import necessary modules and classes

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

PythonC++

import os
import sys
import io
import unittest
from unittest.mock import patch
from contextlib import contextmanager

from SourceCode.DD import DD
from SourceCode.DDStructure.Node import Node
from SourceCode.GraphAlgorithms.ShortestLongestPath.ShortestLongestPath import ShortestLongestPath

from Test.dd_controlled_generators.DDKnapsack import (
    get_exact_dd_knapsack,
    get_reduce_dd_knapsack,
    get_relaxed_dd_knapsack,
    get_restricted_dd_knapsack,
    get_false_dd_knapsack,
)

#include <gtest/gtest.h>
#include "../../Examples/KnapsackInstance/KnapsackProblem.h"
#include "../../SourceCode/DD.h"
#include "GraphAlgorithms/ShortestLongestPath/ShortestLongestPath.h"
#include "dd_controller_generators/DDKnapsack.cpp"

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

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"An exception was raised: {e}")

Warning

This function is just recomended in Python.

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.

KnapsackProblemTest(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])]
        weights: list[int] = [3, 3, 4, 6]
        capacity: int = 6
        self.knapsack_instance = ProblemKnapsack(initial_state=knapsack_initial_state, variables=knapsack_variables, weights=weights, capacity=capacity)
        self.dd_knapsack_instance = DD(self.knapsack_instance)

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

class KnapsackProblemTest : public ::testing::Test {
protected:
    void SetUp() override {
        initial_state = new State({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>`> wheights = {{3, 3, 4, 6}};
        vector `<int>` capacity = 6;
        knapsack_instance = new KnapsackProblemState(*initial_state, variables, wheights, capacity);
        dd_instance = new DD(*knapsack_instance);
        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;
};

4. Implement test methods

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

Example 1:

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_instance.create_decision_diagram()
    self.dd_instance.reduce_decision_diagram(verbose=False)

self.assertTrue(self.dd_instance.get_decision_diagram() == get_reduce_dd_knapsack())

TEST_F(KnapsackStateProblemTest, TestCreateReduceDDGraphEqual) {
    Graph expected_graph = GetReduceDDKnapsackState();
    dd_instance->create_decision_diagram(false);
    dd_instance->reduce_decision_diagram();

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

Example 2:

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

PythonC++

def test_get_solution_for_DD(self):
    self.dd_instance.create_decision_diagram(False)
    objective_weights = [-5, 1, 18, 17]
    value, path = self.get_value_path_solution(objective_weights)


    expected_value: int = 18
    expected_path: str = ' 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, objective_weights):
    shortest_longest_path_instance: ShortestLongestPath = ShortestLongestPath(self.dd_instance)
    shortest_longest_path_instance.set_parameters(objective_weights, "max")


    answer: 'PathStructure' = shortest_longest_path_instance.solve_path()
    return answer.value, answer.path_print

PathStructure`<State>` getLinearDpSolution() {
    vector`<int>` objective_weights = {-5, 1, 18, 17};
    ShortestLongestPath objective_function_instance = ShortestLongestPath`<State>`(*dd_instance);
    objective_function_instance.set_parameters(objective_weights, "max");
    return objective_function_instance.solve_path();
}

TEST_F(ProblemKnapsackTestState, GetSolutionForDD) {
    dd_instance->create_decision_diagram(false);
    PathStructure 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_print, expected_path);
}

5. 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();
}