Skip to content

Resolution proposal of the project from the course unit Algorithms Analysis and Design

License

Notifications You must be signed in to change notification settings

luist18/feup-cal-proj

Repository files navigation

Algorithm Analysis and Design project

GitHub Workflow Status GitHub Workflow Status Travis (.com) Codecov CodeFactor Grade GitHub license

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.

Project description

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.

Project article

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.

Compiling

Dependencies

GraphViewer

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

Google Test is a unit testing library for the C++ programming language, based on the xUnit architecture.

Requirements

  • CMake 3.10.2 or higher
  • Java 8 or higher (used in GraphViewer)

Linux

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.

Windows

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.

Running

Resources and libraries

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.

Program arguments

Map name

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.

Company garage id

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.

Demonstration mode

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.

Running in Linux

./application <map name> <company garage id> [<demonstration mode>]

Running in Windows

.\application.exe <map name> <company garage id> [<demonstration mode>]

Documentation

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 Doxyfile

Testing

The 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.

Examples

1. Company with 4 available vehicles and 10 pick-up points

Company with 4 available vehicles and 10 pick-up points

2. Company with 3 available vehicles and 6 pick-up points

Company with 3 available vehicles and 6 pick-up points

Disclaimer

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.

License

MIT

About

Resolution proposal of the project from the course unit Algorithms Analysis and Design

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •  

Languages