Seite 1 von 3

Aufgabenstellung P1

Verfasst: 9. Nov 2010 16:36
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>"

Re: Aufgabenstellung P1

Verfasst: 10. Nov 2010 18:25
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?

Re: Aufgabenstellung P1

Verfasst: 10. Nov 2010 22:33
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.

Re: Aufgabenstellung P1

Verfasst: 11. Nov 2010 12:02
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.

Re: Aufgabenstellung P1

Verfasst: 14. Nov 2010 16:22
von MisterD123
Bin ich zu blöd um die großen Testfiles auf der Website zu sehen oder sind die noch nicht online? :D

Re: Aufgabenstellung P1

Verfasst: 14. Nov 2010 21:41
von Stille
Die sind noch nicht online. Etwas Geduld bitte noch.

Re: Aufgabenstellung P1

Verfasst: 15. Nov 2010 03:56
von MisterD123
ja, kein Problem. Wollte nur sichergehen dass ich sie nicht einfach völlig übersehe.

Re: Aufgabenstellung P1

Verfasst: 17. Nov 2010 01:24
von Stille

Re: Aufgabenstellung P1

Verfasst: 17. Nov 2010 20:38
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.

Re: Aufgabenstellung P1

Verfasst: 17. Nov 2010 21:22
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.

Re: Aufgabenstellung P1

Verfasst: 17. Nov 2010 22:43
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.

Re: Aufgabenstellung P1

Verfasst: 18. Nov 2010 00:35
von Stille
Tatsache, da ist bei der Konvertierung eine Kante verloren gegangen. Ist gefixt. Danke für den Hinweis und Entschuldigung!

Re: Aufgabenstellung P1

Verfasst: 18. Nov 2010 09:04
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 ;)

Re: Aufgabenstellung P1

Verfasst: 18. Nov 2010 10:54
von Stille
Ja, war spät gestern. Jetzt aber ...

Re: Aufgabenstellung P1

Verfasst: 18. Nov 2010 11:20
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: