Contents:
-
algo.h
- The prototype of the generic algorithm methods.
-
algo.cpp
- Returns the result of Johnson's algorithm applied to the graph. (most optimal choice).
-
dijkstra.cpp
- Implements Dijkstra's algorithm.
-
bellman_ford.cpp
- Implements the Bellman-Ford algorithm.
-
johnson.cpp
- Implements Johnson's algorithm.
-
generator.cpp
- This program generates 10 random tests and computes the algorithms for each of them to determine if their results are equal, thus correct. Then it prints to the output file the result for Johnson's algorithm. Also, the program tests the edge case tests in the "other_tests" folder and prints a corresponding message whether or not the current algorithm can be applied to the input test.
- To test the algorithms and print the result of any other tests it is enough to comment the generateGraph function call in the first for of the main function.
-
Makefile
-
Contains the following rules:
-
generator
- compiles the executable file that will generate the tests and will test every algorithm for the generated tests and the edge case tests
-
run
- runs the test function on every test given as input
-
clean
-
-
-
Folder 'in' containing the input tests (10 tests)
- Each test named "testID.in", where ID represents the number of the test (e.g. test0.in)
- Every test is structured as following:
- First line, V (int - number of oriented graph vertices), V <= 10^5 and E (int - number of edges), E <= max (V^2, 10^6);
- E lines of triplets (src, dest, weight) - exists an edge between src and dest of cost weight;
-
Folder 'out' containing the output tests
- Each test named "testID.in", where ID represents the number of the test (e.g. test0.out)
- Every test contains the adjacency matrix with the minimum distances between every node. If there is no way to reach node j from i, stored -1 in the matrix. (printed it as "inf" in the tests)
-
Folder other_tests
- Contains 3 additional tests that have the same structure as those above but contain edge cases for some/all algorithms such as negative weight edges and negative weight cycles. Their input files are stored in the in folder and the corresponding output files are stored in the out folder.
-
Program logic
- The program is supposed to randomly generate ten different graphs and their edges' weight and compute the three algorithms with the said graph as input. It compares the results of the three matrix generated by them and validates the answer if the outputs are equal. In the output file it either writes the matrix generated by the most efficient algorithm (here Johnson), or it writes the reason why a certain algorithm cannot be computed on a given input (see other_tests).