Dr. Andreas Borchert Abteilung Angewandte Informationsverarbeitung 2. Dezember 2002
Ingo Melzer Blatt 6


Uni Logo



OO-Datenbank Anwendungen (WS 2002)


Abgabetermin 9. Dezember 2002

Die Welt ist klein (20 Punkte)

Vor einigen Jahren war die Suche nach Schauspielern mit einer hohen Kevin Bacon Nummer beliebt. Dabei geht es um die Suche nach dem kürzesten Weg zwischen zwei Personen, wobei die Anzahl der Sprünge über andere Personen gezählt werden. Wenn also A B kennt und B C kennt, so ist der Abstand zwischen A und C zwei. Um dieses Spiel zu spielen, haben wir entsprechende Daten zu Anna Karenina von Leo Tolstoy, David Copperfield von Charles Dickens, Homer, Huckleberry Finn von Mark Twain und Les Misérables von Victor Hugo auf unserem FTP-Server gelegt. Diese stammen von der Stanford GraphBase von Donald E. Knuth.

Schreiben Sie nun ein Perl Skript, das zuerst eine dieser Dateien einliest, dann ein Kürzel einer beteiligten Person bekommt und dann schrittweise die transitive Hülle dieser Person bestimmt (und natürlich ausgibt). Dies könnte z. B. so aussehen:

thales$ ./related.pl huck.dat 
The following persons have been found: AB, AP, AS, AT, BD, BE, BG, BH,
BI, BK, BM, BN, BO, BP, BR, BS, BT, BU, CG, CS, DH, DR, DU, HF, HI, HS,
HT, HW, JG, JH, JI, JK, JL, JM, JN, JO, JP, JT, JY, KI, LB, LI, LZ, MA,
MC, MH, MJ, MP, MR, MS, MW, NT, OD, PA, PW, RG, RH, SD, SI, SP, SR, SS,
SU, SW, TB, TC, TF, TG, TP, TS, TU, WB, WD, WW.
Please enter the person's key: AB
AB knows in 0 steps: AB 
AB knows in 1 steps: BN DH DR DU HF JO KI MJ PW SW TF WB 
AB knows in 2 steps: AP AS AT BD BE BG BH BI BK BM BO BP BR BS BT BU CG
CS HI HS HT HW JG JH JI JK JL JM JN JP JT JY LB LI LZ MA MC MH MP MR MS
MW NT OD PA RG RH SD SI SP SR SS SU TB TC TG TP TS TU WD WW
thales$


Noch ein paar Tips:



Ingo Melzer 2002-12-02