Optimal road itineraries using Contraction Hierarchies

Resources

A tiny example dataset: test.csv
A real dataset: data.csv
Specification of the roads.csv file
Small C++ header (LOG, CHECK()..) that you can copy and include.
Expected output of PrintHistogram() of the total degrees (out-degree + in-degree) of the nodes of the graph obtained from data.csv.
Same thing, for the smaller test.csv.
To compute the distance between two lat/lngs: Haversine Formula (quick link) and Mean Earth Radius.
Expected sum of all the arc durations (in seconds) on the graphs obtained from data.csv: about 612965.047217.
For test.csv, the expected sum is 2410.100641.
C++ code snippets to get started with Graphs and Dijkstra. Use them!
test.sh, to verify that your "server" binary works.

Objectives: Day 1

Before 12:30, deliver the Graph class, which must follow exactly the API I gave.
I will give a correction at 12:30, and we'll move on.
Two files to send: graph.h, graph.cc. You must name them exactly like that.
Pack them in a .zip archive and send them to fabien.viger@gmail.com. Make sure you include all your @epitech.eu email addresses in the email!

To test your code: download graph_test.cc and base.h, and run graph_test.cc
Example: g++ -std=c++11 -Ofast graph.cc graph_test.cc && ./a.out
before 18:00, deliver the part of the server that parses the data and prints some info (see below)
I will (automatically) run the following commands on your archive:
```
unzip archive.zip
make server
./server data.csv
```
I will actually use an other dataset than the data.csv I gave you.

Your server should take the name of the .csv file as argument. It can output anything it wants on stderr (I won't look at it).
Upon startup, your server should output the following 3 lines on stdout:
- The number of nodes in the road graph (this is not the number of points!)
- The number of arcs in the road graph
- The sum of all arc durations, in seconds.
I will give partial credit (i.e. some points in the final grade) for every correct line.

Reminder: Expected NumNodes / NumArcs / Sum of arc durations
- test.csv: 6 nodes / 20 arcs / 2410.100641 seconds
- data.csv: 36315 nodes / 308646 arcs / 612965.047217 seconds
For reference: the distance between lat/lngs (33, 1) and (-45,-9) is 8731841.391016 m.

Objectives: Day 2

Before 09:30, deliver objective 2) of Day 1 (email to fabien.viger@gmail.com)
I will give a reference solution at 09:45 (when we start), which you can use. These parts won't be graded after that.
Before 17:30: Deliver an archive with:
- dijkstra.h and dijkstra.cc, both working with dijkstra_test.cc
- The Makefile and the server code so that your server, after startup (and outputting the 3 lines #nodes, #arcs, sum of arc durations), should enter its interactive mode:
  It will read queries on stdin of the form (one query per line)
```
48.3456,2.3456->-56.9876,10.4500\n
```
  Where each lat/lng will be the lat/lng of a node of the road graph (i.e. a lat/lng that is the first or last point of the road, or a lat/lng that appears at least twice in the dataset (possibly on the same road)).
  - If the query is valid (each lat/lng corresponds exactly to a node of the road graph), your server should output on stdout the total duration of the shortest path on the road graph between these nodes, in seconds (eg. 6345.23718).
    I will verify the answer with a precision of 0.01. Be careful with that: cout << x doesn't output a double with a lot of accuracy. Use printf("%.6lf") instead.
  - If the lat/lngs are valid nodes of the graph, but there is no path, you server should output NO PATH
  - If the query is invalid (bad format, or invalid lat/lng, or lat/lng not found in the input data), your server should output a line starting with INVALID on stdout.
  Use test.sh to test your server: bash test.sh ./server. WARNING: it does not test everything. In particular, it does not verify the path description (i.e. the list of arc lengths along the path), it checks only the length of the shortest path. Also, it only sends one query! Your server must support multiple queries, I will test for that.
  
  To get a better score, your server can, next to the total path duration, output the space-separated list of arc durations along the shortest path. Be careful: I want the natural order, i.e. if the shortest path is 0->1->2, I want the arc duration of 0->1, then the arc duration of 1->2.
  
  The answer to one query should be on a single line. The answers to the next query will be on the next output line (and so on).
I will provide and comment a reference solution for the Dijkstra library at 17:30, then I will explain how the bidirectional Dijkstra works.
Until Sunday at midnight: The second part of the last objective, i.e. the interactive server.
Also until Sunday at midnight: Bi-directional Dijkstra.
Fill the BidirectionalDijkstra class in bidi_dijkstra.h, and implement it in bidi_dijkstra.cc.
You can test it with bidi_dijkstra_test.cc

Grading

Each objective (Day1 @12:30, Day1 @18:00; Day 2 @09:30, Day2 @17:30, and final delivery on Sunday @23:59) counts, with various coefficients. You don't need to do everything perfectly to get a perfect grade (yet I don't expect many groups to get a perfect grade: this is hard).
You are guaranteed to get a passing grade if you:
- Fully complete the final objective, i.e. implement a fuly correct and efficient bi-directional Dijkstra with a good stopping criterion, and use it in your server to answer queries.
- OR you successfully completed all the Day1 and Day2 objectives.