How ALGator Works

The ALGator system is designed to evaluate the quality of algorithms for solving various problems. It runs selected algorithms on chosen test data, recording performance metrics such as execution time and result quality in output files. Using additional tools within the ALGator system, users can analyze these outputs and generate reports in the form of tables and graphs.

To solve a specific problem (e.g., sorting numbers, matrix multiplication, shortest path in a graph, traveling salesman, etc.), a user creates a project in the ALGator system. Using text configuration files and Java classes, the user defines:

Properties of the input,
Properties of the output,
Test case generators,
Test sets (concrete inputs and expected outputs),
Performance indicators, and
Algorithms for solving the given problem.

Once the project is set up, users can add new test sets and implement new algorithms. The ALGator system ensures that all implemented algorithms are executed in the same execution environment.

The following sections describe these project features in more detail.

1. Properties of the Input

The input to the algorithm is defined by a set of parameters and a data part.

1.a Input Parameters

Input parameters (InputParameters) determine the nature of the input (e.g., table size, graph density, number of input bits, etc.). They are used both during automatic algorithm execution (e.g., to find the largest input size processable within one second) and during result analysis (e.g., plotting complexity graphs based on input size). Users specify parameters in the proj/testcase.json file—listing the names in the "InputParameters" table and precisely describing each parameter in the "Parameters" table, including its type and range (minimum, maximum, and default value). The order in the "InputParameters" table is important, as parameters are output in this order.

Example: In the BasicSort project, the testcase.json file describes a parameter defining the input table size as follows:

{
  "Name":        "N",
  "Description": "The size of the test (number of elements to be sorted)",
  "Type":        "int",
  "Meta":        {"Min":1000, "Max":1000000000000, "Step":1000, "Default":5000}
}

1.b Data Part of Input

The data part of the input is defined in the Java class proj/src/Input.java as an attribute that carries the input data. The attribute's type depends on the input data type (e.g., int[] for a table of numbers, int[][] for a two-dimensional matrix, etc.). The Input.java class typically also defines a constructor for easier input handling.

Example: In the BasicSort project, the data carrier and constructor in the Input.java class are defined as:

public int[] arrayToSort;

public BasicSortInput(int[] data) {
    this.arrayToSort = data;
}

2. Properties of the Output

The algorithm output is represented by the src/Output.java class. The output data is typically stored in one attribute. Its type depends on the output generated by the algorithm (e.g., int for an integer output, String for text output, etc.). The Output.java class usually includes a constructor for convenient output handling.

Example: In the BasicSort project, the data carrier and constructor in the Output.java class are:

public int[] sortedArray;

public BasicSortOutput(int[] data) {
    sortedArray = data;
}

3. Test Case Generators

A test case (an object of the TestCase class) in the ALGator system consists of an input (an object of the Input class) and optionally an expected output (an object of the Output class). Test cases are created during algorithm execution using generators—methods that accept generating parameters and return a corresponding test case.

A project can include multiple generators. The basic generator (which must be present) is the type 0 generator (Type0), which takes all input parameters as generating parameters.

Example: In the BasicSort project, there are two input parameters: N (input size) and DIST (describing how "shuffled" the data is). The type 0 generator creates input of size N with distribution DIST.

Besides the basic generator, a project may have other generators (types 1, 2, 3, etc.) that accept different generating parameters. Their role is to create test cases by determining input parameter values and populating the data part accordingly.

Example: In the BasicSort project, input can also be created by reading data from a file. In this case, the generator requires only one parameter—the file name. It reads the data, creates the data part, and sets input parameters: N (number of data items) and DIST=RND (random shuffle).

Generators may add additional properties to the input for filtering during analysis, such as the type of generator used or the source file name.

Generators of type i are implemented in proj/src/TestCaseGenerator_Typei.java in the method generateTestCase(Variables generatingParameters).

Information about defined generators (their types and required parameters) is stored in proj/testcase.json in the "Generators" table. Parameter properties are also defined there in the "Parameters" table.

4. Test Sets

Test cases in the ALGator system are grouped into test sets (TestSet), which are the basic units for algorithm execution. Usually, an algorithm is run on all test cases within a test set. Each test set is defined by two files: tests/<T>.json and tests/<T>.txt, where <T> is the test set name (e.g., TestSet1). The JSON file contains administrative data (set name, description) and:

"N" — number of inputs in the test set,
"TestRepeat" — number of repetitions per input, and
"TimeLimit" — maximum allowed execution time per input (execution stops if exceeded).

In the file tests/<T>.txt, individual test cases are recorded—each line describes one test case. The number of actual lines (non-comments) in this file must match the value of "N" from the json file. A test case is presented with a single text line (testcase_description_line), containing the following data:

type:test_name:generating_parameters

where:

type: the type of the generator that will create the test case (default: Type0),
test_name: the name of the test (default: ""), and
generating_parameters: parameters passed to the generator creating the test case; their order and meaning are provided in the testcase.json file at the generator definition.

Example: In the BasicSort project, two test cases are described in the file TestSet1.txt with the following lines:

Type0:test1:10:SOR
Type1:test3:numbers.rnd

The first test case will create the default generator (parameter values: N=10, DIST=SOR), and the second test case will create a generator of type 1 (parameter value: filename="numbers.rnd").

Additional files used for test generation (for example, the file numbers.rnd from the above example) are located in the tests directory and its subdirectories. They are referenced relative to the tests directory in the generator method using the generating parameter TESTS_PATH.

4.a Expected Algorithm Output

When checking the correctness of the result returned by an algorithm, knowledge of the correct result (expected output) is necessary. The user can ensure that it is generated by a generator and saved as part of a test case. When checking correctness, both the algorithm's output and the expected output will be available for comparison.

For example, in a matrix multiplication project to verify correctness, we need matrix C (to compare with the algorithm's output). Since calculating matrix C every time would be time-consuming, we create it once and save it in a file presented as part of the test case. The file is then read by the test case generator, and the data is stored in expectedOutput (an object of the Output class). When checking correctness, we compare the algorithm-generated matrix with the matrix in expectedOutput.

Example: In the BasicMatrixMul project, a generator of type 1 is defined with the following generating parameters:

"GeneratingParameters": ["N", "FilenameA", "FilenameB", "FilenameC"]

The test case description line (<T>.txt file) provides the matrix sizes and three filenames (the first two contain matrices to multiply, the third contains the result), like this:

Type1:test1:100:ts1/rnd-100-2-A:ts1/rnd-100-2-B:ts1/rnd-100-2-C

The generator of type 1 reads all three matrices:

int [][] A = BasicMatrixMulTools.readMatrixS(path, filenameA);
int [][] B = BasicMatrixMulTools.readMatrixS(path, filenameB);
int [][] C = BasicMatrixMulTools.readMatrixS(path, filenameC);

and stores the input (matrices A and B) and the expected output (matrix C) in the test case.

5. Performance Indicators

The quality of an individual algorithm is measured using execution indicators (such as time, used space, number of steps, etc.). For execution time values, ALGator provides them automatically, while other indicators must be defined and calculated by the user.

5.a Time Consumption Indicators

ALGator runs each algorithm multiple times on a given test case (parameter TestRepeat in the file tests/<T>.json) and records various times (time of the first execution (FIRST), average execution time (AVG), maximum execution time (MAX), etc.). The user must specify in the result_em.json file which of these times should be displayed in the execution results.

Example: In the BasicSort project, we are interested in the time of the first execution of the algorithms, so in the "Indicators" table in the result_em.json file, among other things, the indicator Tfirst is defined as follows:

{
  "Name"         : "Tfirst",
  "Description"  : "Sorting FIRST time",
  "Type"         : "timer",
  "Meta"         : {"ID" : 0, "STAT": "FIRST"}
}

The parameter name Tfirst is also specified in the "IndicatorsOrder" table (determining the display order of this parameter in result files).

5.b Other Indicators

For other indicators (measuring, for example, the quality of the output), the user must provide both definitions in the mentioned json file and the source code that calculates the indicator value based on the test case data and the algorithm's output. The code for calculating the value of the <ind> indicator is written in the file proj/src/IndicatorTest_<ind> in the getValue() method.

6. Algorithms

The core of the algorithm in the ALGator system is a method that receives an object of the Input class as input and returns an object of the Output class.

Algorithm <A> is defined in the algs/ALG-<A> directory, specifically with the configuration file algorithm.json and the Java file src/Algorithm.java, in which the method is defined as follows:

Output execute(Input input) {...}

The task of this method is to create and return the output based on the received input. The execution time of this method is considered as the execution time of the algorithm.

7. Result Analysis and Reporting

After running algorithms on the test sets, the ALGator system produces output files containing performance data. Users can utilize built-in tools to analyze this data, generating tables and graphical reports to compare algorithm performance and quality.

The system supports filtering, sorting, and grouping of results based on input parameters and performance indicators. This flexibility helps users gain insights into algorithm behavior under different conditions.