- Ausgabe: 08.12.2015
- Abgabe: 18.12.2015 23:50 Uhr (Bereitstellen auf GitHub)
- Das Testat erfolgt offline
Weil Sie die Aufgaben der Verschlüsselung beim Bundesnachrichtendienst so gut gelöst haben, eilt Ihnen der Ruf eines hervorragenden Programmierers in Geheimdienstkreisen voraus. Während einer Exkursion nach Moskau werden Sie an einem schneereichen Tag von einem Herrn im langen Trenchcoat angesprochen, der Ihnen eine lukrative Arbeit in den USA anbietet.
Ihr neuer Arbeitgeber ist eine Sicherheitsagentur aus den Vereinigten Staaten, die aus diversen Gründen ungenannt bleiben möchte. Das Ziel Ihrer Aufgabe besteht darin, in einem Geflecht von Beziehungen (einem gerichteten Graphen) nach bestimmten Eigenschaften zu suchen. Da man Ihnen nicht verraten möchte, welche Daten letztendlich in dem Graphen gespeichert werden, müssen Sie mit generischen Typen arbeiten. So hat die Agentur später die Möglichkeit, beliebige Daten in Ihrem Werkzeug zu speichern und zu suchen.
Ein Graph besteht aus Knoten (Node). Jeder Knoten hat einen Namen (String) und einen Wert beliebigen Typs - hier wird die Agentur später ihre eigenen Datentypen verwenden. Weiterhin hat der Knoten beliebig viele Kinder. Um den Knoten typsicher zu gestalten, soll er als generische Klasse implementiert werden, sodass der Typ des im Knoten gespeicherten Werts eindeutig festgelegt werden kann.
Jeder Knoten hat folgende Methoden:
addChild- Hinzufügen eines KindknotensgetChildren- Auslesen aller KindknotengetName- Auslesen des Namens des KnotensgetValue- Auslesen des Wertes des Knotens
Implementieren Sie eine entsprechende generische Klasse Node mit den genannten Methoden. Für die Verwaltung der Kinder verwenden Sie bitte intern und auch in der Schnittstelle für die Rückgabewerte die weiter unten beschriebenen Listen.
Der Graph besteht aus einer beliebigen Anzahl von Knoten, wobei einer der Knoten als Anfangsknoten ausgezeichnet wird (root node). Von diesem Anfangsknoten aus können Sie alle anderen Knoten erreichen. Der Graph besitzt folgende Methoden:
search- Suchen nach allen Knoten mit einem bestimmten Wert. Das Suchverfahren soll hierbei von Außen mitgegeben werden können (siehe unten).copyInto- Kopieren aller Knote in eine übergebene Liste.
Für die Suche im Graphen schreiben Sie bitte ein Interface SearchStrategy. Dieses Interface hat zwei Methoden. Zum einen kann man, ausgehend von einem Startknoten, den Graphen nach Knoten mit einem bestimmten Wert durchsuchen und bekommt alle passenden Knoten zurück (search); zum anderen kann man den Weg den die Suche beim letzten Durchlauf durch den Graphen genommen hat auslesen (getPath).
Implementieren Sie danach das Interface für eine Suchstrategie, nämlich die
Tiefensuche. Sollten Sie noch Langeweile haben, können Sie optional auch noch eine Breitensuche implementieren.
Hinweis: Denken Sie daran, dass es sich um einen gerichteten Graphen handelt, der Zyklen enthalten kann. Sie müssen daher bei der Suche entsprechende Vorkehrungen treffen, um nicht in eine Endlosschleife bzw. unendliche Rekursion zu geraten.
Für die Verwaltung von Listen, sowohl von Knoten, als auch von anderen Objekten, benötigen Sie entsprechende Klassen und Interfaces. Implementieren Sie daher in einem ersten Schritt das Interface List für die Verwaltung von Listen mit der Klasse ListImpl.
Erstellen Sie nun eine spezialisierte Version des Interfaces (NodeList), die nur Knoten verwalten kann. Implementieren Sie auch diese mit der Klasse NodeListImpl.
Achtung: Sie können erhebliche Implementierungsaufwände sparen, wenn Sie eine geschickte Vererbungsbeziehung zu der Klasse java.util.LinkedList eingehen.
Testen Sie Ihre Implementierung mit Unit-Tests. Zeigen Sie auch, anhand des in der folgenden Abbildung dargestellten Graphen, dass Ihre Breiten- bzw. Tiefensuche die Knoten in der erwarteten Reihenfolge besuchen.
- Tiefensuche: [A, B, E, H, I, F, J, K, G, C, L, M, N, D, O, P]
- (optional) Breitensuche: [A, B, C, D, E, F, G, L, M, O, P, H, I, J, K, N]
Die folgende Abbildung zeigt einen beispielhaften Graphen.
Simulieren Sie diesen Graphen und gehen Sie davon aus, dass der im Knoten gespeicherte Wert seinem Namen entspricht. Suchen Sie dann den Knoten "`K"' und geben Sie den Suchpfad sowohl für die Tiefensuche aus. (Falls Sie auch noch die Breitensuche implementiert haben, geben Sie auch diesen Pfad aus.)