README.md

   1 # C++ Routenplanungs-Basis-Framework
   2
   3 In diesem GIT-Repository finden Sie eine kleine Codebasis die Sie zur Bearbeitung des Übungsblatts verwenden sollen.
   4 Der Ihnen zur Verfügung gestellt Code besteht aus mehreren Dateien:
   5 `constants.h`,
   6 `timer.h`,
   7 `id_queue.h`,
   8 `vector_io.h`,
   9 `decode_vector.cpp`,
  10 `encode_vector.cpp`,
  11 `compare_vector.cpp` und
  12 `compile.sh`.
  13
  14 In `constants.h` werden zwei oft verwendete Konstanten definiert: `invalid_id` und `inf_weight`.
  15 Erstere gibt eine ungültige ID an und letztere stellt eine unendliche Länge dar.
  16 `inf_weight` ist so gewählt, dass die Konstante verdoppelt werden kann, ohne einen Überlauf zu verursachen, d.h., der Ausdruck `inf_weight < inf_weight+inf_weight` ist unproblematisch.
  17 In der Datei `timer.h` gibt es eine Funktion die die aktuelle Zeit misst (Alternativ können Sie die Funktionen aus dem `<chrono>`-Header verwenden.).
  18 Diese kann verwendet werden um die Laufzeit ihres Codes zu messen.
  19 Die Datei `id_queue.h` enthält eine Prioritätswarteschlange (`std::priority_queue` ist problematisch für unseren Anwendungsfall, da sie keine `decrease_key` Operation besitzt).
  20 Die restlichen Dateien dienen dem Einlesen und der Ausgabe von Daten.
  21 Jede Datendatei ist das binäre Abbild eines `std::vector`s im Speicher, d.h., ein Vektor von 100 `int`s wird in einer Datei gespeichert die genau 400 Byte lang (Wir gehen stets davon aus, dass ein int 32 Bit hat.) ist.
  22 In `vector_io.h` werden die Funktionen `load_vector` und `save_vector` zur Verfügung gestellt.
  23 Diese können Sie wie folgt verwenden:
  24
  25 ```C++
  26 vector<unsigned> head = load_vector<unsigned>("arc_head_file_name");
  27 vector<float> lat = load_vector<float>("node_latitude_file_name");
  28 save_vector("my_new_file_name", head);
  29 ```
  30
  31 Die restlichen Dateien stellen Hilfsprogramme dar.
  32 `encode_vector` und `decode_vector` konvertieren Vektoren von und zu textuellen Darstellungen.
  33 Das Programm `compare_vector` vergleicht ob zwei Vektoren identisch sind und wenn sie es nicht sind gibt es eine Übersicht über die Unterschiede.
  34 Die Datei `compile.sh` ist ein Shellskript das die drei Programme übersetzt.
  35 Erweitern Sie `compile.sh` so, dass es auch die von Ihnen erstellten Programme übersetzt.
  36
  37 ## Graphen
  38
  39 Knoten und Kanten werden durch numerische IDs identifiziert, die von `0` bis `n-1` bzw. `m-1` gehen, wobei `n` die Anzahl an Knoten und `m` die Anzahl an gerichteten Kanten ist.
  40 Wir speichern gewichtete und gerichtete Graphen in einer Ajdazenzarraydarstellung.
  41 Ein gerichteter und gewichteter Graph besteht aus 3 Vektoren.
  42 Diese heißen `first_out`, `head` und `weight`.
  43 Um über die ausgehenden Kanten eines Knoten zu iterieren können Sie den folgenden Code verwenden:
  44
  45 ```C++
  46 vector<unsigned> first_out = load_vector<unsigned>("first_out_file_name");
  47 vector<unsigned> head = load_vector<unsigned>("head_file_name");
  48 vector<unsigned> weight = load_vector<unsigned>("weight_file_name");
  49
  50 unsigned my_node = 42;
  51 for(unsigned out_arc = first_out[my_node]; out_arc < first_out[my_node+1]; ++out_arc){
  52     cout<< "There is an arc from " << my_node
  53         << " to " << head[out_arc]
  54         << " with weight " << weight[out_arc]
  55         << endl;
  56 }
  57 ```
  58
  59 **Hinweis**: `head` und `weight` haben so viel Elemente wie es Kanten gibt.
  60 `first_out` hat ein Element mehr als es Knoten gibt.
  61 Das erste Element von `first_out` ist immer 0 und das letzte ist die Anzahl an Kanten.
  62 Für alle Graphen gibt es zwei unterschiedliche Kantengewichte: Reisezeit und Reiselänge.
  63 Des Weiteren gibt es für manche Graphen zusätzliche für jeden Knoten die geographische Position.
  64 Diese wird als zwei `float` Vektoren abgespeichert die für jeden Knoten den Längen- und Breitengrad angeben.
  65
  66 Im Verzeichnis `/algoDaten/praktikum/graph` liegen die Daten von mehreren Graphen in diesem Format.
  67 Manche dienen nur zu Testzwecken während andere zur Aufgabenbewertung verwendet werden.
  68 Die Testgraphen entsprechen ganz grob Stupferich, Karlsruhe\&Umgebung, Deutschland\&Umgebung und (West-)Europa.
  69 Die Aufgabengraphen haben die Größe des Deutschlandgraphen.
  70
  71 **Achtung**: Der Europagraph könnte zu groß sein für den Hauptspeicher von manchen Poolraumrechnern.
  72
  73 ## Hinweise zur Nutzung im Routenplanungspraktikum
  74
  75 Zu jeder Aufgabe sollen Sie den Quellcode ihrer Programme und die berechneten Lösungen abgeben.
  76 Der Quellcode soll durch das Ausführen von `./compile.sh` auf einem der Poolraumrechner übersetzt werden können.
  77 Auf den Poolraumrechner ist ein GCC 7.3.1 installiert.
  78 Dieser unterstützt C++17 vollständig.
  79 Neuere C++ Features die nicht vom Compiler unterstützt werden sind nicht erlaubt.
  80 Das verwenden extern Bibliotheken ist nicht erlaubt.
  81 Die C++-Standardbibliothek is nicht extern.