\( \newcommand{\dist}{\textnormal{dist}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\pfrac}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \)

6. Graphen

6.6 Programmierprojekt: Längste Pfade in DAGs

Im Englischen lassen sich schöne Wortketten bilden, in dem man in einem Wort einen Buchstaben rausstreicht und so wiederum ein neues Wort enthält. Hier ist ein Beispiel: 

whines
whine 
wine 
win 
in

Dies ist nicht die längste derartige Kette. In diesem Projekt wollen wir Java-Programme schreiben, die für eine gegebene Wortliste die längste derartige Kette finden. Als erstes müssen wir erkennen, dass es sich hier um ein Graphenproblem handelt. Was ist der Graph? Die Knoten sind die Vokabeln, und die gerichteten Kanten sind, naja, sehen Sie selbst:

Der vollständige Graph ist natürlich viel größer.

Übungsaufgabe Schreiben Sie ein Programm ReadVocabularyDigraph.java, das eine Liste von Vokabeln einliest und daraus den "Lösche-einen-Buchstaben"-Digraphen baut. Die Liste hat folgendes Format: 

weaves
eaves
braver
weave 
braver 
grave 
ave 
wave 
rave 
gave

Also einfach eine Liste von Vokabeln, eine pro Zeile, nicht notwendigerweise sortiert. Ihr Programm soll ein Digraph-Objekt wie in Digraph.java erstellen. Das Wort grave soll zu einem Knoten mit dem Namen grave und Raus-Nachbarn gave, rave, ... und den Rein-Nachbarn graves, gravel, ... werden.

Ihr Programm die Anzahl der Kanten im Digraph ausgeben.

Testen Sie Ihr Programm auf der Vokabeldatei englishVocabulary.txt.

Übungsaufgabe Schreiben Sie ein Programm DigraphNavigator.java. Dieses soll von System.in einen Knotennamen lesen und dann, in zwei Zeilen, alle Raus-Nachbarn und Rein-Nachbarn anzeigen, also 

java DigraphNavigator < englishVocabulary.txt
grave
outNeighbors: rave, gave
inNeighbors: gravel, graves
grav
Error: couldn't find "grav" in file "englishVocabulry.txt

Ihr Programm soll noch zwei Sonderbefehle $max-in und $max-out haben, die Listen der Wörter mit maximalen In-Degree und Out-Degree ausgeben.

Übungsaufgabe Beschreiben Sie einen Algorithmus, der, gegeben einen DAG \(G=(V,E)\) und einen Knoten \(u \in V\) einen längsten mit \(u\) beginnenden Pfad findet. Ihr Algorithmus sollte effizient sein, idealerweise also Laufzeit \(O(n+m)\) haben.

Übungsaufgabe Erklären Sie, warum Ihr Algorithmus auf zyklischen Graphen nicht funktioniert.

Übungsaufgabe Beschreiben Sie einen Algorithmus, der, gegeben einen DAG \(G=(V,E)\), einen längsten Pfad in \(G\) findet.

Hinweis: rufen Sie nicht einfach den Algorithmus der vorherigen Übungsaufgabe für jeden Knoten auf. Dies würde zu einer Laufzeit \(O(n(n+m))\) führen. Beschreiben Sie einen Algorithmus mit Laufzeit \(O(n+m)\).

Übungsaufgabe Implementieren Sie Ihre zwei vorherigen Algorithmen als Java-Programm! Im speziellen: schreiben Sie ein Programm FindLongestPath.java, das die englische Vokabelliste einliest und dann vom User ein Wort einliest und den längsten mit diesem Wort beginnenden Pfad ausgibt, also beim Input whines beispielsweise whines, whine, wine, win, in, I

Übungsaufgabe Modifizieren Sie Ihr Programm so, dass es nun statt Wörtern vom User auch Zahlen einliest. Bei Eingabe einer Zahl \(k\) soll es die Menge aller Wörter ausgeben, die den Anfang eines Pfades der Länge 5 bilden. Bei Eingabe von 6 soll also unter Anderem das Wort whines ausgegeben werden.