Aufgabenstellung P1

Moderator: Effiziente Graphenalgorithmen

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Aufgabenstellung P1

Beitrag von Stille »

Hallo,

kleines Edit zur (evtl. unklaren) Aufgabenstellung:

- Sie dürfen keine Algorithmen aus Bibliotheken verwenden außer einem Sortierverfahren zur Sortierung der Kanten nach Gewicht.
- Der Aufruf in Aufgabe 2 soll 'MSTComp <infile>' sein.
- Meinetwegen können Sie die Wahl des Verfahrens auch in einem Parameter "-a" angeben, also in etwa:
"MST -a Kruskal <infile>"
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Render
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 12. Okt 2008 17:21

Re: Aufgabenstellung P1

Beitrag von Render »

Zwei kurze Fragen:
Zählen so Dinge wie priority queues/heaps zu Algorithmen (die wir nicht benutzen dürfen) oder zu Datenstrukturen?
Ich wollte spaßeshalber die Boost Graph Library verwenden, ist das okay?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

Hallo,

Queues, Heaps, Stacks, etc. sind Datenstrukturen. Sie können sie einfach benutzen.

Die BGL für C++ ist ok. Es wäre sicherlich interessant, spaßeshalber einen Laufzeitvergleich Ihrer Implementierungen mit den BGL Algorithmen zu machen.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Aufgabenstellung P1

Beitrag von yourmaninamsterdam »

Es sollte zwar eigentlich klar sein, aber weil ich immer mal wieder in den Hausübungen auf sowas stoße:

Ein Aufruf einer Methode an Objekten, die von einer Bibliotheksklasse instanziiert sind, unterliegt natürlich entsprechenden Laufzeiten. Beachtet das bei der Implementierung. Das gilt natürlich insbesondere für insert, remove etc. auf Datenstrukturen. Es kann z.B. auch sein, dass remove(id) eine andere Laufzeit hat als remove(Object) weil der Index in konstanter Zeit gefunden wird und nach dem Objekt erst (in linearer Zeit) gesucht werden muss.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

Bin ich zu blöd um die großen Testfiles auf der Website zu sehen oder sind die noch nicht online? :D

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

Die sind noch nicht online. Etwas Geduld bitte noch.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

ja, kein Problem. Wollte nur sichergehen dass ich sie nicht einfach völlig übersehe.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

empfehlung für nächstes jahr: schreibt bereits in der aufgabenstellung, dass man mit mehrfachkanten umgehen können soll :D

/edit: öhhh blöde frage aber meine algorithmen sagen mir (alle drei) dass die großen graphen 2 und 3 nicht zusammenhängend wären: Stimmt das? oO für alle anderen testfälle liefern sie sonst das richtige ergebnis, deswegen wundert mich das grade ein wenig. Ich werd mal später nen kurzen scanning algo schreiben oder so und das ausprobieren glaub ich.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

MisterD123 hat geschrieben:empfehlung für nächstes jahr: schreibt bereits in der aufgabenstellung, dass man mit mehrfachkanten umgehen können soll :D
Sind ja nur vereinzelte Spezialfälle. Sollte aber klar sein, dass Mehrfachkanten in MST-Algorithmen eigentlich keine Rolle spielen.
MisterD123 hat geschrieben: öhhh blöde frage aber meine algorithmen sagen mir (alle drei) dass die großen graphen 2 und 3 nicht zusammenhängend wären: Stimmt das? oO für alle anderen testfälle liefern sie sonst das richtige ergebnis, deswegen wundert mich das grade ein wenig. Ich werd mal später nen kurzen scanning algo schreiben oder so und das ausprobieren glaub ich.
Das würde mich sehr wundern, denn es handelt sich um die Daten von Strassennetzwerken in den USA. Geben Sie doch mal Bescheid, wenn Sie zu einem Ergebnis gekommen sind.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

Meine Algorithmen hatten recht :) Ergebnisse Zusammenhangsanalysen:

Großer graph 1: 264346 Knoten
Komponente 0: Startknoten 0, 264346 Knoten

Großer graph 2: 435666 Knoten
Komponente 0: Startknoten 0, 1 Knoten
Komponente 1: Startknoten 1, 435665 Knoten

Großer graph 3: 1070376 Knoten
Komponente 0: Startknoten 0, 1 Knoten
Komponente 1: Startknoten 1, 1070375 Knoten

=> In den großen Graphen 2 und 3 hat "v 0" jeweils keine inzidente Kante, die Graphen sind also in der Tat nicht zusammenhängend. Ist aber nur ein "off by one" problem, die Graphen an sich sind intakt wenn man Knoten 0 rauswirft.
Sagt bitte bescheid wie/wann ihr die Dateien entsprechend geändert habt, oder ob wir solche Fehler ignorieren sollen.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

Tatsache, da ist bei der Konvertierung eine Kante verloren gegangen. Ist gefixt. Danke für den Hinweis und Entschuldigung!
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung P1

Beitrag von MisterD123 »

muss nochmal meckern =)

MST2.ug -> Input error: Graph was supposed to contain 528532 edges. 528533 edge lines were read and graph contains 528533 edges.
MST3.ug -> Input error: Graph was supposed to contain 1356398 edges. 1356399 edge lines were read and graph contains 1356399 edges.

=> das "m" in der header-zeile wurde bei beiden graphen-beschreibungen vergessen anzupassen ;)

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Aufgabenstellung P1

Beitrag von Stille »

Ja, war spät gestern. Jetzt aber ...
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

murphy
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 9. Nov 2005 13:58

Re: Aufgabenstellung P1

Beitrag von murphy »

Hallo zusammen,

mich würde interessieren ob denn schon jemand von euch etwas zur Leistung seiner Implementierung sagen kann (grobe Größenordnungen beispielsweise fürs Einlesen der großen Graphen und Laufzeiten der darauf anzuwendenden Algorithmen). Zu letzterem kann ich leider noch nix sagen, aber das Einlesen der großen Graphen dauert bei mir mehrere Minuten, was sicher noch ein wenig optimierungsbedürftig ist... :wink:

Antworten

Zurück zu „Effiziente Graphenalgorithmen“