Aufgabenstellung P1

[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>"

[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?

[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.

[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.

[MisterD123]

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

[Stille]

Die sind noch nicht online. Etwas Geduld bitte noch.

[MisterD123]

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

[Stille]

Die Testcases sind nun online: http://www.algo.informatik.tu-darmstadt ... nd-uebung/

[MisterD123]

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

/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.

[Stille]

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

Sind ja nur vereinzelte Spezialfälle. Sollte aber klar sein, dass Mehrfachkanten in MST-Algorithmen eigentlich keine Rolle spielen.

ö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.

[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.

[Stille]

Tatsache, da ist bei der Konvertierung eine Kante verloren gegangen. Ist gefixt. Danke für den Hinweis und Entschuldigung!

[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

[Stille]

Ja, war spät gestern. Jetzt aber ...

[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...