# Programmierkurs Aufgaben
- Graphen als struct implementieren (1-1:30h)
- Adjazenzmatrix
- Strings fuer die Knoten
- Algorithmen
- Zusammenhangskomponenten
- Tiefensuche (45 Minuten)
- Spannbaum nach Prim (45 Minuten)
- Dijkstra (1,5h purer Dijkstra, 1h für Ausgabe)
- ~~Floyd~~
# Aufgaben
## Ein- / Ausgabe von Graphen
Zum Testen Ihrer Implementierungen gibt es die Hilfsbibliothek `graphio.h`, mit der Sie Graphen eingeben, speichern und visuell darstellen können.
Machen Sie sich mit der Bibliothek vertraut.
Die .txt Dateien sind nach einem bestimmten Schema aufgebaut. Diese Dateien können Sie modifizieren oder erstellen und dann einlesen.
```
<number of vertices>
<vertex 1>
<vertex 2>
<vertex ...>
<adjacency matrix>
```
als Beispiel:
```
5
A
B
C
D
E
0 5 -1 1 -1
1 0 3 -1 10
2 1 0 5 -1
-1 -1 -1 0 -1
7 -1 9 -1 2
```
Ein eingelesener Graph kann zu einer .dot Datei umgewandelt werden, um sie im Anschluss **visuell darstellen** zu können.
Dafür können Sie folgenden Seite benutzen: https://dreampuf.github.io/GraphvizOnline/
Dort kopieren Sie den Inhalt einer .dot Datei in die linke Hälfte und der Graph wird rechts gerendert.
Das obige Beispiel gerendet würde zum Beispiel so aussehen:
## 1. Graphenrepräsentierung in C
Vorgabe:
Das angegebene struct repräsentiert einen Graphen g. Dabei werden in `names` die string-Repräsentationen der Knoten des Graphen gespeichert. Bei `matrix` handelt es sich um die Adjazenzmatrix des Graphen, sie beinhaltet welche Knoten mit welchen Distanzen miteinander verbunden sind. Dabei gilt, dass Zeilen- und Spaltenposition eines Knoten in der Matrix jeweils der Position des Knotens in dem `names`-Array entspricht.
```c=
/**
* representation of a graph using a list of vertices and an
* adjacency matrix
*/
typedef struct {
int **matrix;
char **names;
int size;
} GRAPH;
GRAPH *graph_create();
void graph_destroy(GRAPH *g);
int graph_enlarge(GRAPH *g);
int graph_add_vertex(GRAPH *g, char *name);
void graph_add_edge_sym(GRAPH *g, int v1, int v2, int dist);
void graph_add_edge(GRAPH *g, int v1, int v2, int dist);
int graph_get_dist(GRAPH *g, int v1, int v2);
char* graph_get_name(GRAPH *g, int index);
int graph_is_undir(GRAPH *g);
```
Implementieren der folgenden Verwaltungsfunktionen:
### a)
```c
GRAPH *graph_create();
```
welche genug Speicherplatz für ein GRAPH struct reserviert und matrix und names mit NULL, sowie size mit 0 initialisiert. Bei Erfolg wird ein Zeiger auf den Speicherbereich zurückgegeben, sonst wird NULL zurückgegeben.
### b)
```c
void graph_destory(GRAPH *g);
```
welche sämtliche durch g verwalteten Speicherplatz wieder freigibt.
Tipp: `free(NULL)` richtet keinen Schaden an.
### c)
```c
int graph_enlarge(GRAPH *g);
```
vergrößert den Graphen, sodass ein weiterer Knoten Platz hat. Gibt im Fehlerfall 0 zurück und gibt den gesamten Graphen frei, gibt ansonsten die neue Größe des Graphen zurück.
Tipp: Der Tipp von matrix_destroy kann beim Aufräumen hilfreich sein, und laesst sich auch auf realloc übertragen.
### d)
```c
int graph_add_vertex(GRAPH *g, char *name);
```
fügt dem Graphen einen neuen Knoten **ohne anfängliche Kanten** (also Einträge über Verbindungen zu diesem Knoten = `-1`) mit dem übergebenen Namen hinzu. Die Funktion gibt im Fehlerfall -1 zurück (und räumt ggf. auf), ansonsten gibt sie den Index des hinzugefügten Knoten zurück.
### e)
```c
void graph_add_edge(GRAPH *g, int v1, int v2, int dist);
```
fügt dem Graphen eine gerichtete Kante ausgehend von `v1` nach `v2` hinzu. `v1` und `v2` sind die jeweiligen Indizes der Knoten.
### f)
```c
void graph_add_edge_sym(GRAPH *g, int v1, int v2, int dist);
```
fügt dem Graphen eine ungerichtete Kante zwischen `v1` und `v2` hinzu. `v1` und `v2` sind die jeweiligen Indizes der Knoten.
### g)
```c
int graph_get_dist(GRAPH *g, int v1, int v2);
```
welche die Distanz des Weges von `v1` nach `v2` zurückgibt.
### h)
```c
char* graph_get_name(GRAPH *g, int index);
```
welche den Namen des Knotens mit dem entsprechenden Index zurückgibt.
### i)
```c
int graph_is_undir(GRAPH *g)
```
welche überprüft ob ein Graph g ungerichtet ist oder nicht. (Ein Graph ist ungerichtet wenn all seine Kanten ungerichtet sind.)
Die Funktion soll bei einem ungerichteten Graph eine Wert ungleich `0`, bei einem gerichteten Graph `0` zurückgeben.
### Lösungen
Siehe `graph.c` und `graph.h`
### j)
Schreiben Sie ein Hauptprogramm in eine neue C-Datei (`graph_create.c`), welches folgende Graphen erstellt, als Datei speichert und eine entsprechende .dot Datei erstellt.
graph1:
graph2:
### Lösung
Siehe `graph_create.c`
## 2. Zusammenhangskomponenten
### a)
Implementieren sie eine Funktion, welche die Zusammenhangskomponenten eines Graphen zurückgibt.
Tipp: Dies kann in Form eines Feldes mit `size` Komponenten geschehen, wobei ein Eintrag mit `n` and der Stelle `0` bedeutet, dass der 1. Knoten (also mit Index `0`) zur Zusammenhangskomponente `n` gehört.
### b)
Der Pokemontrainer Ash hat seine Reise in der Hoenn-Region begonnen. Da er noch kein Pokemon besitzt, welches Surfer einsetzen kann, möchte er wissen, welche Orte er alles von Wurzelheim (Index = 0) aus besuchen kann. Eine Karte der Hoenn-Region ohne Surfer finden Sie in der Daten`hoenn_ohne_surfer.txt`, bzw. `hoenn_ohne_surfer.dot`.
Schreiben Sie ein Hauptprogramm welches die Zusammenhangskomponenten der Hoenn-Region, nach Komponente sortiert, ausgibt. (Zur Bearbeitung der folgenden Aufgaben empfiehlt es sich dieses Hauptprogramm geteilt von den anderen Funktionen in einer getrennten C Datei zu schreiben)
### c)
Implementieren Sie eine Funktion, welche zurückgibt ob ein übergebener Graph zusammenhängend ist oder nicht.
### d)
Implementieren Sie Funktionen (in einer neuen C Datei), welche einen minimalen Spannbaum zu einem übergebenen Graphen generiert und diesen zurückgibt. Verwenden Sie dabei den Algorithmus nach Prim (https://de.wikipedia.org/wiki/Algorithmus_von_Prim). Der übergebene Graph soll dabei unverändert bleiben. Fangen sie mögliche Fehlerhafte Eigenschaften und Zustände des übergebenen Graphen ab (wie z.B. ein unzusammenhängender Graph).
Bei Graphen, welche nicht zusammenhängend sind kann der Algorithmus von Prim nicht sinnvoll angewendet werden, daher soll die Methode nichts zurückgeben.
Tipp: eine Funktion zum kopieren eines Graphen ohne seine Kanten bietet sich an.
### Lösung
a-c): Siehe `traversal.c` und `traversal.h` und `traversal_main.c`
d): Siehe `mst.c` und `mst.h`
## 3. Wegsuche mit Dijkstra
Sie sollen im folgenden eine Funktion implementieren, welche den kürzesten Weg von einem Knoten `vstart` zu allen anderen Knoten im Graph ermittelt. Verwenden Sie hierfür den Dijkstra-Algorithmus.
### a)
Überlegen Sie sich sinnvolle Hilfsfunktionen mit Hilfe des Stoffs.
### b)
Implementieren Sie alle oben gefundenen Hilfsfunktionen.
### c)
Implementieren Sie den Dijkstra-Algorithmus.
(Von der Funktion soll eine Liste zurückgegeben werden, welche an jedem Index `i` der Liste den nächsten Knoten auf dem kürzesten Weg von `i` nach `vstart`.)
### d)
Wandeln Sie die Rückgabe des Dijkstra-Algorithmus in eine Liste der abzulaufenden Knoten vom Start zu einem Zielknoten um.
### e)
Implementieren Sie ein Funktion, welche die einzelnen Stationen von einem Startknoten zu einem Zeilknoten und dessen Gesamtlänge auf Kommandozeile ausgibt.
### f)
Pokemon Trainer Ash ist nach seiner langen Reise durch die Hoenn-Region alle 8 Orden beisammen und besucht seine Rivalin Maike zu Hause in Wurzelheim (Index = 0). Danach möchte er so schnell wie möglich zur Pokemon Liga (Index = 16). Leider ist der Schlotberg wieder ausgebrochen, deshalb kann er nicht dorthin fliegen. Er möchte nun den schnellstmögliche Weg herausfinden. Surfer steht ihm an diesem Punkt selbstverständlich zur Verfügung.
Implementieren Sie ein Hauptprogramm welches ihm den Weg und die Gesamtstrecke auf die Kommandozeile ausgibt. Die Karte der Hoenn-Region finden Sie in der Datei `hoenn.txt`, bzw. `hoenn.dot`.
(Eine sinnvolle Aufteilung, sowie Pseudocode finden Sie hier: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus)
### Lösung
siehe `navigator.c` und `navigator.h`
Sign in with Wallet
Connect another wallet