- Project name: PortoCityTransfers
- Short description: Console-based program to manage a shuttle company
- Environment: Unix/Windows console
- Tools: C++
- Institution: FEUP
- Course: CAL (Algorithm Design and Analysis)
- Project grade: 19.2/20.0
- Group members:
| The original map, as rendered by OpenStreetMap | As rendered by our program |
|---|---|
 |
 |
view - Types of roads |
speed - Maximum allowed speed |
|---|---|
 |
 |
path - Shortest path |
path -v - Nodes visited by each shortest path algorithm |
|---|---|
 |
 |
reduce - Close-up view |
ride - Check ride path |
|---|---|
 |
 |
scc - Train station strongly connected component
|
Closeup, near Freixo Bridge |
|---|---|
|
|
| Closeup, near A41 and A32 (Sandim, V. N. Gaia) | |
|
If you are cloning from GitHub, you should pull all submodules with
git submodule update --init --recursive # If for the first timemake # Compile all dependencies and libraries
make clean # Cleanup files (except submodules and map/)
make cleanall # Cleanup all files
make test # Run unit testsmake automatically downloads the sample map file map.xml we used to develop this project, using wget. You must install wget to properly get the file, or otherwise download map.zip from this link, unzip it and copy its content to map/original.
You can use some of these locations to explore most functionalities of this program:
| Location | Municipality | Node number |
|---|---|---|
| Monte Crasto | Gondomar | 2454698517 |
| Casa Branca de Gramido | Gondomar | 1551005098 |
| Maia city hall | Maia | 5272120014 |
| Porto Airport | Maia | 4102094652 |
| SONAE | Maia | 5702537845 |
| Zoo Maia | Maia | 4551001973 |
| EXPONOR | Matosinhos | 1436599811 |
| Fábrica Unicer | Matosinhos | 7186948192 |
| NorteShopping | Matosinhos | 4606348154 |
| Port of Leixões | Matosinhos | 4612166056 |
| Fábrica Nortada | Porto | 286968787 |
| FCUP | Porto | 128672575 |
| FEUP | Porto | 4523960191 |
| Palácio de Cristal | Porto | 3391598673 |
| São João Baptista Fortress | Porto | 4567051363 |
| Serra de Santa Justa | Valongo | 6426059706 |
| Afurada marina | Vila Nova de Gaia | 1143316550 |
| Monastery of Serra do Pilar | Vila Nova de Gaia | 3398946056 |
| Sandeman | Vila Nova de Gaia | 1143316550 |
| Senhor da Pedra beach | Vila Nova de Gaia | 4764305642 |
| Zoo Santo Inácio | Vila Nova de Gaia | 1324797708 |
For all graphical uses, FLAGS flags which roads to draw (add them to combine):
| Type of road | Description | Flag |
|---|---|---|
| Motorway | Red | 1 |
| Trunk | Pink | 2 |
| Primary | Orange | 4 |
| Secondary | Yellow | 8 |
| Tertiary | Gray | 16 |
| Road | Gray | 32 |
| Residential | Gray | 64 |
| Slow | Gray, dashed | 128 |
./main view FRACTION FLAGS
FRACTION Fraction of nodes to draw (improves display performance).
FLAGS Flag which roads to draw (add them to combine).
- To see all types of roads with a fraction of 5, run
./main view 5 255 - To see all main roads with a fraction of 3, run
./main view 3 15
./main speed FRACTION FLAGS
FRACTION Fraction of nodes to draw (improves display performance).
FLAGS Flag which roads to draw (add them to combine).
Roads are coloured according to the following table:
| Speed [km/h] (up to) | Colour |
|---|---|
| 120 | Red |
| 100 | Orange |
| 80 | Yellow |
| 60 | Green |
| 50 | Black |
| 40 | Gray |
./main scc FRACTION FLAGS
FRACTION Fraction of nodes to draw (improves display performance).
FLAGS Flag which roads to draw (add them to combine).
Roads are coloured red if they connect two nodes in the train station's SCC, or gray otherwise.
./main scc FRACTION FLAGS SOUR DEST [-v]
./main scc FRACTION FLAGS SOUR_LAT SOUR_LON DEST_LAT DEST_LON [-v]
FRACTION Fraction of nodes to draw (improves display performance).
FLAGS Flag which roads to draw (add them to combine).
SOUR Source node (beginning) of the path we are looking for.
SOUR_LAT Latitude of the source coordinate.
SOUR_LON Longitude of the source coordinate.
DEST Destination (end) of the path we are looking for.
DEST_LAT Latitude of the destination coordinate.
DEST_LON Longitude of the destination coordinate.
-v Colour visited nodes according to the algorithms that explored them.
You can use either ./main scc FRACTION FLAGS SOUR DEST [-v] or ./main scc FRACTION FLAGS SOUR_LAT SOUR_LON DEST_LAT DEST_LON [-v], where the second option is similar to the first, with only the extra step of finding, for the source and destination coordinates, the closest nodes of the graph that are connected to the train station.
Roads are coloured according to the following table:
| Algorithm | Path colour | Visited nodes colour |
|---|---|---|
| Dijkstra's algorithm with early stop | Black | Pink |
| A* algorithm, 90km/h | Black | Red |
| A* algorithm, 60km/h | Magenta | Magenta |
| A* algorithm, 30km/h | Blue | Blue |
| A* algorithm, 10km/h | Cyan | Cyan |
- To get paths between FEUP and FCUP, you can run either of
./main path 1 255 4523960191 128672575
./main path 1 255 41.1777 -8.598 41.1522 -8.6361./main reduced allows to see the reduced version of the connected graph. This reduced graph was an early effort with the objective of rapidly finding the distance between any two nodes, by reducing the original graph by removing middle nodes in one-way and two-way roads.
./main ride FRACTION FLAGS RIDES NUM_RIDES
FRACTION Fraction of nodes to draw (improves display performance).
FLAGS Flag which roads to draw (add them to combine).
RIDES Rides file path (output).
NUM_RIDES Number of ride to be drawn.
Draws ride NUM_RIDES from file RIDES.
./main ride 1 255 resources/it1_03.rides 1./main (iteration1 | iteration2) CLIENTS VANS RIDES
CLIENTS Clients file path (input).
VANS Vans file path (input).
RIDES Rides file path (output).
- To get all rides serving clients in
resources/it1_01.clients, using vansresources/it1_01.vansand outputting those rides toresources/it1_01.rides, run
./main iteration1 resources/it1_01.vans resources/it1_01.clients resources/it1_01.ridesOther examples:
./main iteration1 resources/it1_01.vans resources/it1_02.clients resources/it1_02.rides #Takes around 5 seconds
./main iteration1 resources/it1_01.vans resources/it1_03.clients resources/it1_03.rides #Takes around 8 seconds
./main iteration2 resources/it2_01.vans resources/it1_03.clients resources/it2_01.rides #Takes around 8 seconds
./main iteration2 resources/it2_01.vans resources/it2_01.clients resources/it2_02.rides #Takes around 20 seconds
./main iteration2 resources/it2_01.vans resources/it2_02.clients resources/it2_03.rides #Takes around 35 secondsReports are compiled by Github Actions, to see them go to Actions > Workflows > Compile reports, go to the most recent action and check This run > Artifacts.
You can also check the releases.
© 2020 Diogo Rodrigues, João António Sousa, Rafael Ribeiro
All files are licensed under GNU General Public License v3, to the exception of:
- submodules, which are subject to specific licenses
- map data, which was extracted from OpenStreetMap under the Open Database License; refer to the report for further details