This repository comprises the second part of the Algorithm Analysis and Design course unit project. The goal was to create a solution for a specific problem applying the object-oriented paradigm in C++ and algorithm design.
The theme approached in the problem is a particularization of the Travelling Salesman Problem, the Vehicle Routing Problem with Pick-up and Delivery. This repository contains the algorithm solution for that problem as well as an application related to the problem.
A more theoretical study of the problem can accessed here. The study contains all the information related to the algorithm development process as well as the conceptual business model.
GraphViewer is a tool for graph visualization based on the JUNG framework, in the context of the Algorithm Design and Analysis course, at FEUP. It has been developed and mantained over the years by the course's Teaching Assistant students.
Google Test is a unit testing library for the C++ programming language, based on the xUnit architecture.
- CMake 3.10.2 or higher
- Java 8 or higher (used in GraphViewer)
To compile a linux executable file run the build.sh script in the root directory. The output files are going to be stored in the build directory.
To compile a linux executable file run the winbuild.sh script in the root directory. The output files are going to be stored in the winbuild directory.
The maps must be placed in the resources directory. The GraphViewer jar file must be placed in the lib directory. Both directories have to be in the same directory as the executable file.
The name of the map to run the application. There are currently two maps in the resources. A small map around FEUP, resources/Porto. And a highly connected graph with the city of Porto, resources/Porto_strong.
Values: Porto and Porto_strong.
The location ID of the company's garage. The location ID of a node is defined in the nodes.txt file of a map.
Values: any ID in the nodes.txt file of a map.
When defined true the application bootstraps a default company client with a set of predefined pick-up points. This argument is optional.
Values: true of false.
./application <map name> <company garage id> [<demonstration mode>].\application.exe <map name> <company garage id> [<demonstration mode>]The code documentation is generated with doxygen. Doxygen is a third-party documentation tool, thus, it is necessary a previous installation in order to be able to get the documentation. A standard project doxygen configuration file is located in the 'docs' directory under the name doxyfile. Currently, the documentation is only exported in HTML. After exporting the files are stored in the docs directory.
Here is an example of how to export the documentation with the standard project doxygen configuration file:
cd doc
doxygen DoxyfileThe unit tests are perfomed by Google Test, the Google's C++ test framework. Currently, the version used is the latest.
The code coverage can be consulted by clicking the coverage badge in the header.
This repository contains the C++ solution for the problem. Note that it might contain errors and should not be used as a solution for anyone besides the authors.