Dr. Matthias Grabert Abteilung Angewandte Informationsverarbeitung 28. November 2002
Johannes Mayer Blatt 6






Objektorientierte Softwareentwicklung mit C++ (WS 2002/2003)


Abgabetermin: 5. Dezember 2002

1 Isser oder hat er? (3 Punkte)

Entscheiden Sie jeweils, ob die Begriffe in einer ,,Is-A``- oder ,,Part-of``-Beziehung zueinander stehen. Zeichnen Sie für die ,,Is-A``-Beziehungen einen einfachen Abhängigkeitsgraphen und bilden Sie dadurch eine mögliche Klassenhierarchie bezüglich Ober- und Unterklassen.

1. LKW, Pkw, Auto, Reifen, Motor, Dreirad, Fahrrad, Fahrzeug, Fahrer, Antriebsachse
2. Getränkekiste, Sprudelflasche, Bierflasche, Flasche, Verschluss, Volumen
3. Konzert, Besucher, Sänger, Person, Security-Guard, Manager, Schuhe, Kleidung

2 Erdös-Zahlen (7 Punkte)

Implementieren sie eine Klasse für ungerichtete Graphen, die Methoden enthählt, um

• Knoten einzufügen, entfernen, zählen und suchen,
• Kanten einzufügen, entfernen, zählen und suchen und
• die Entfernung aller Knoten von einem gegebenen Knoten zu bestimmen.

Unter Verwendung dieser Klasse sollen nun für Beispieldaten die Erdös-Zahlen (siehe letztes Übungsblatt) berechnet werden. Ihr Programm erhählt die Daten von der Standardeingabe. Diese enthalten die folgenden (durch Whitespace getrennten) Felder:

1. Anzahl der Autoren (Integer)
2. je Autor: Name des Autors (String ohne Whitespaces)
3. Anzahl der Paper (Integer)
4. und je Paper:
   1. Anzahl der Autoren (Integer)
   2. Titel des Papers (String ohne Whitespaces)
   3. je Autor: Nummern des Autors (Integer)
      (Die Autoren werden mit 0 beginnend nummeriert.)

(Erdös ist immer der erste Autor in allen Datensätzen!)
Beispiel für eine Eingabe:

2
Erdos
Thomasius
3
2 Mein_erstes_Paper 0 1
1 Noch_so'n_Paper 0
1 Weiteres_Paper 1

Daraus erstellen Sie dann einen Publikationsgraphen, in dem zwei Autoren genau dann durch eine Kante verbunden sind, wenn sie zusammen publiziert haben, und bestimmen mit der bereits implementierten Abstandsmethode die Erdös-Zahlen aller Autoren. (Beachten Sie, dass es auch Autoren mit Erdös-Zahl unendlich gibt.) Danach sollen jeweils Erdös-Zahl und Autor durch einen Tabulator getrennt in einer eigenen Zeile ausgegeben werden, wobei die Autoren in alphabetischer Reihenfolge erscheinen sollen.

Tipps:

• Sie dürfen nun die Klassen string, vector und map aus der STL verwenden.
• Bei der Entfernungsbestimmung sollten Sie sich merken, welche Knoten schon besucht wurden, damit die Suche auch terminiert und nicht in einen Zyklus gerät.
• Die Entfernungsbestimmung kann folgendermaßen druchgeführt werden:
  1. Setze die Entfernung des Knoten, zu dem die Entfernung bestimmt werden soll, auf 0.
  2. Suche die noch nicht besuchten Nachbarn aller Knoten mit der bisher höchsten Entfernung (am Anfang 0) und weise ihnen eine um 1 größere Entfernung zu.
  3. Wiederhole den letzten Schritt solange, bis keine weiteren Knoten mehr hinzukommen.
  Dabei müssen nicht alle Knoten durchlaufen werden, sondern nur die von dem gegebenen Knoten aus erreichbaren!
• Zu den Beispieleingaben erdos.ta bis erdos.tj sind jeweils zur Überprüfung die Ausgaben gegeben. Diese können mit dem Kommando diff mit dem eigenen Ergebnis verglichen werden.
• Ein Iterator einer map, deren Schlüssel vom Typ string sind, durchläuft die Schlüssel in alphabetischer Reihenfolge.