Application designed to simulate a service wich provides the users with the best path from one point to another (in a city for example), taking into account various aspects such as time, distance and expenditure between different modes of transportation.
When starting the application, the user is presented with the start up menu in which he can choose which environment (graph) he wants to work with, either with a real data map (option 1) or with a test one (option 2).
The next set of choices is equal in both environments, the difference between them being in the map used:
- Experimental Graph (Real Data) - Here the map will be generated using real data taken from https://www.openstreetmap.org of a portion of the city of Porto. This data was converted in .txt files using a combination of two C# parsers, one of them provided by João Carvalho (@jflcarvalho). However, some "artificial" data had to be created for better visualization of the results. This data consists of additional pedestrian paths connectingthe subway to near regular paths.
- Custom Test Graph - This a much smaller, "handmade" graph created for testing purposes only.
- Exit - The application will terminate.
Selecting any of the first two options will bring up the respective map in a new window. The user can move around the map by left clicking anywhere and dragging the mouse. He can also zoom in and out with mouse wheel.
Note: From here on out, we will be using the first option since it is the most interesting one.
In the graphviewer window, each node is represented by a yellow dot (with a small '.' tag above) and each edge by a colored line connecting two nodes. Each edge color indicates a different mean of transportation:
- Red - Pedestrian path/road.
- Green - Subway.
- Blue - Bus route.
Note: In this graph, we do not differentiate between one way or two way paths for simplicity. Also, keep in mind that, although unrealistic, the bus routes connecting each pair of nodes are not considered as roads as well so as to give a better visualization of the results.
This menu gives the user the option to calculate a new route or to exit the application.
If the user chooses the firs option, he will be propted to pick the origin point. He can do this by indicating the street name or the ID of the node. In the experimental graph it is recommended to choose the firt option and in the test one the second option (in the test graph the nodes have their ID above them. This was not done in the experimental graph so as not to clutter the map).
If the user picked an origin point by its street name, he will be given the choice to execute an exact or approximate search of that name.
- Exact Search - The application will search for names that are equal to or contain the string given using the Knuth-Morris-Pratt's algorithm.
- Approximate Search - The application will search for similar names to the one given.
After that, the user can choose to list all the results returned or just a top 5 of the most accurate ones (recommended option) ordered by similarity.
He should then choose one of the results.
After that, the user will be prompted to pick a destination in the same fashion.
After both points are sucessfully picked, the user can choose which path suits him the best:
-
Shortest Path - The application will only take in consideration the distance between each node, returning the shortest path between the origin and destination.
-
Best Path - By choosing this option, the app will take into account not only the distance between each node but also the walking distance, reaching a balance between the two.
-
Quickest Path - Here the app will only take into consideration the time that it takes to travel between each node, minimizing the overall time it takes to travel from the origin to the destination.
Note: All public transports have a 2 minute waiting time associated.
After choosing one of these options, the user can customize his path based on another set of attributes:
-
Transport Preferences - The user can indicate his prefered transportation method: bus or subway.
-
Spending Limit - The user can set a maximum amount of money he can spend. The pre-defined price is of 1.20€/hour (just like in the city of Porto).
After setting everything up (or not), the user can choose the 3rd option to calculate the path. The results are computed using highly customized versions of Dijkstra's algorithm and are shown in two different ways:
- In the console window, through text indications. Here it also present the time it takes to traverse each different section of the path (sections are delimited by different transportation methods).
- In the graphviewer window. The origin node is represented in blue, the destination in black and the path nodes in green. Each of these nodes is also increased in size.
The user is then returned to the main menu.
After cloning the repo, in order to compile the project, you'll need to set your character set to "Not set" or equivalent. Also, you'll need to include the ws2_32 library in the project.
To use only the executable, you only need to make sure the .exe is in the same folder as the text files and the graphviewer.jar. After that just run it like any other executable.