BUG in isForest

[089]

Bitte fixen, falls noch Zeit und Lust:

Für graphtoolGui -iml "[0 1 1 1 1 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 1 1 1 0; 1 0 0 0 0 1 1 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 1 0]" -na gibt die Function hasCycle() true statt false aus (siehe #57. Das führt dazu, dass auch deine Funktion nicht gut funktioniert.

Im Codeteil

    if(hasCycle() || !isDirected()) {
        isForestFlag = false;
        return false;
    }

bin ich mir nicht ganz sicher, ob !isDirected() an der Stelle richtig ist. Warum sollte ein ungerichteter Graph ohne weitere Überprüfung kein Wald sein (siehe Beispiel oben)?

[Areiser]

Ein ungerichteter Graph kann kein Wald sein, der Wald ist auch nur "gerichtet" definiert. Ungerichtet wäre jede Kante ein Zyklus (der wird bloß nicht gezählt nach der Definition eines Zyklus in ungerichteten Graphen).

Der Fehler wäre also wenn in hasCycle, isForest prüft nur, ob es sich um einen gerichteten Wald handelt. Soll ich die vielleicht umbenennen, damit es klarer ist?

[089]

Doch kann er schon (siehe https://de.wikipedia.org/wiki/Wald_(Graphentheorie) oder Kapitel III, Folie 5, Ezparza/TUM/WS13/14)

Definition: Ein ungerichteter Graph heißt Baum, falls G zusammenhängend und kreisfrei ist. Die Knoten von mit Grad 1 heißen Blätter (leaves).

und

Wälder Definition: Ein Graph, dessen (Zusammenhangs-) Komponenten jeweils Bäume sind, heißt Wald.

[Areiser]

Oh.. ok, dann ist das nur in unserem Skript so definiert. In dem Fall könnte ich das rausnehmen, aber dann stimmt hasCycle nicht... Was meinst du? Ich hab ja eigentlich auch überall geschrieben, dass die Methode prüft ob es sich um einen gerichteten Wald handelt.

[089]

Dann nehmen wir die beiden (hasCycle() und isForest()) raus.