**HINWEIS: Im WS 18/19 bieten wir die VL Algorithm Engineering an, in der erklärt wird, wie schnelles Routing bei Google, Apple, … funktioniert. **
Im Rahmen dieses Programmierprojektes wird in Gruppen von jeweils 2-3 Personen ein webbasierter Routenplaner implementiert.
Das Projekt verläuft in 3 Phasen, jede Gruppe muss nach Ende einer Phase die entsprechende Aufgabe fertiggestellt haben, um weiter am Programmierprojekt teilnehmen zu dürfen.
Formalien
Die Abgaben müssen in einer Form erfolgen, welche Übersetzung und Ausführung auf einem Ubuntu 16.04 System ermöglicht (gilt für alle Phasen). Entsprechende Dokumentation sowie Makefiles o.ä. sind beizufügen; es sind nur Bibliotheken erlaubt, welche in den Standard-Repositories von Ubuntu zur Verfügung stehen. Falls Sie aktuell über kein Ubuntu System verfügen, können Sie ein solches auch in einer Virtuellen Maschine auf ihrem Rechner installieren oder aber auch eine virtuelle Maschine der bwcloud (s.u.) nutzen.
Hardware
In dieser Veranstaltung werden Sie mit etwas größeren Datenmengen zu tun haben. Falls ihr Rechner weniger als 8GB RAM zur Verfügung hat, könnte es für die größeren Datensätze problematisch werden. Als Student haben sie jedoch die Möglichkeit, in der bwcloud eine VM mit 16GB RAM (Stand 2017) zu nutzen (als Ubuntu 16.04 Image).
Gruppeneinteilung
| Gruppe | Teilnehmer | Phase 1 | Phase 2 | Phase 3 |
|---|---|---|---|---|
| A | R.R., T.W. | OK | OK | OK |
| B | C.S., D.G. | OK | OK | OK |
| C | P.S., L.S. | OK | OK | OK |
| D | S.B., M.A. | OK | OK | OK |
| E | C.B., L.N. | OK | OK | OK |
| F | F.H., R.L. | OK | OK | OK |
| G | J.H., D.S. | OK | OK | OK |
| H | S.K., M.S. | OK | OK | OK |
| I | L.Gr., M.T. | OK | OK | OK |
| J | J.W., L.Ge. | OK | OK | OK |
| K | A.S., A.R. | OK | OK | OK |
| L | M.K., J.K. | OK | Nachfrage | Nachfrage |
| M | Y.B., E.M. E.C. | OK | OK | OK |
| N | ||||
| O | ||||
| P | ||||
| Q |
Phase I (Deadline 10.06.2018)
Erstellung der Routenplanungskomponente;
Abgabe muss bestehen aus:
- einem gepackten Archiv mit allen Sourcen (keine Graphdaten) im .zip oder .tar.bz2 Format
- einem README, welches
- die Übersetzung auf einem Ubuntu 16.04 System erklärt
- die Benutzung erläutert
- Kriterien für das Bestehen von Phase I (alles bzgl. Deutschland-Datensatz):
- Implementierung muss auch für den Deutschland-Datensatz auf einem Rechner mit 16GB RAM lauffähig sein
- Einlesen des Deutschland-Graphen darf maximal 2 Minuten dauern
- Korrekte Berechnung eines one-to-all Dijkstra darf nicht mehr als 20 Sekunden dauern (i5 Haswell, 3.2 GHZ, Ubuntu 16.04, 16GB RAM)
- Die Implementierung muss es erlauben, sowohl Start-Ziel-Anfragen zu stellen, als auch Dijkstra von einem Knoten zu allen anderen Knoten zu berechnen (unter Angabe der benötigten Zeit) sowie danach Distanzen vom Startknoten abzufragen
- desweiteren muss es die Möglichkeit geben, eine Datei mit Start-Ziel-Anfragen einzulesen und die Distanzen auszugeben (siehe bereitgestellte .que bzw. .sol Dateien): .que/.sol-Dateien; Aufruf z.B. mit ./myBenchmarker bw.fmi bw.que; die Ausgabe sollte dann bw.sol entsprechen.
- Die Abgabe muss als Archiv (<1MB, ohne Graphdaten), welches den Gruppennamen (z.B. A.zip) trägt, erfolgen
Phase II (Deadline 30.06.2018)
Erstellung der Webclientkomponente. Abgabe kann zeitgleich mit Phase III erfolgen!
Phase III (Deadline 31.08.2018)
Erstellung der Webserverkomponente.