This project is based on the final project required in the subject Data Structures and Algorithms 1 at Tampere University. Shortly, my work covered the content appearing in datastructures.hh and datastructures.c in which I implemented the needed data structures and functions for the correct functionality of the given GUI.
Note: Final function of the project specified later on may not print correctly some of the test cases, but overall it works fine.
In this project I implemented the necessary data structures and operations so that train stations, train departures and administrative regions can be added to the program, and furthermore train connections between stations can be created and shown based on different preferences. The goal of the project is to run every single function of the project with less than
During this README file I will mostly go over some of the most important features in which the project is based on, rather than the description of each function and their asymtotical efficiency can be found on the definition of the function in the datastructures.hh file.
If you want to get visual output of what the input commands print out, then it's preferable that Qt is used since the GUI of this project was created with Qt designer by the course staff. Other IDEs could be used but then the output would be only numerical.
In order to start running the program, you would need to open with Qt creator the pro file. Then, the same interface guides the user when clicking in any function operation, as it can be seen in the following image:
If you want to run several commands at once, then inside the functional-tests folder you could find some test functions that through the option read can be computed all at once. For this, the test file to be used would need to be moved to the main project folder, so that it can bw tracked by the project.
Most features of this project have been based on the use of STL library.
Main containers used have been map and unordered_map given their cheap cost for addition,removal and find operations.
std::unordered_map<StationID, Station*> stations;Most of the used unordered_maps have used the standard hashing provided rules, but others have been based on the hash-table provided by the course staff for coordinates management.
std::map<Time, Station*> fromNeighbours;Maps instead have been used as red-black trees, suitable for efficient sorting trees based on time.
In order to avoid expensive iterative operations, all the mainly used operations have been based on the STL built-in algorithms library, and also specific functions of each container used.
const auto& comparisons = [](const auto& left_sta,const auto& right_sta){
Distance distL = std::sqrt(std::pow(left_sta->locationXY.x, 2) + std::pow(left_sta->locationXY.y, 2));
Distance distR = std::sqrt(std::pow(right_sta->locationXY.x, 2) + std::pow(right_sta->locationXY.y, 2));
if (distL != distR){
return distL < distR;
}
else {
if (left_sta->locationXY.y <= right_sta->locationXY.y){
return distL < distR;
}
else {return distR < distL;}
}
};
std::sort(unsorted.begin(), unsorted.end(), comparisons);In this project all the necessary objects (Station, Region, Train...) have been produced as data structures to store all the needed attributes:
struct Station {
StationID stationid = NO_STATION;
Name stationName = NO_NAME;
Coord locationXY = NO_COORD;
std::unordered_map<TrainID, Time> departures;
RegionID region = NO_REGION;
SearchInfo* search_info;
Station* parentNode = nullptr;
// Each next station and the departure time.
std::vector<std::pair<Station*, Time>>toNeighbours;
std::map<Time, Station*> fromNeighbours;
};Regional organization, stations' order and trains' itinerary are based on tree rules that, require tree-based traversal logic, when it comes to search efficiently for a specific result. Some of the algorithms used are listed below, for further information on them, wikipedia links with their logic have been attached at the end.
Used in functions route_any & route_least_stations, it searches for the first existing route from a source station and a ending station, which turns to be the shortest path in terms of number of stations.
Used in function route_with_cycle, it shows the path that the train would do to make the cycle, that is, stopping by the same station more than once.
Used in function route_shortest_distance, it finds the shortest route between two stations based on the distance weight, which is calculated through the Euclidean distance.
This project should be seen from a data-structures and algorithms backed perspective. Indeed, all the implemented code has been based on this part of the project.
Also, if there's interest on knowing all the asymptotic efficiencies of each function, they can be found in the header file datastructures.hh with a short rationale.
- Data Structures and Algorithms 1 (FITech) | Tampere universities (tuni.fi)
- cppreference.com
- Breadth-first search - Wikipedia
- Dutch Direct: Celebrating the 50th anniversary of Dijkstra's Shortest Path algorithm - Gridshore
- Graphs - Depth-first search: cycle finding - Competitive Programming | INGInious