Seite 1 von 2

3. Praktikum - Was macht Test 2 ?

Verfasst: 15. Mai 2007 10:18
von Abo
Ich habe mein Programm hochgeladen und bekomme beim Test2 folgende Fehler-Meldung:

--------------------------------------------------------------------
Testsuite: Test_2
Tests run: 2, Failures: 2, Errors: 0, Time elapsed: 0.056 sec

Testcase: test_TopDown took 0.014 sec
FAILED
your topological sort contains some nodes multiple times
junit.framework.AssertionFailedError: your topological sort contains some nodes multiple times
at TestHelper.validTopsort(Unknown Source)
at Test_2.test_TopDown(Unknown Source)

Testcase: test_BottomUp took 0.002 sec
FAILED
your topological sort contains some nodes multiple times
junit.framework.AssertionFailedError: your topological sort contains some nodes multiple times
at TestHelper.validTopsort(Unknown Source)
at Test_2.test_BottomUp(Unknown Source)

--------------------------------------------------------------------

Eigentlich aus meiner Sicht fange ich alle möglichen Fehler ab, die man sich vorstellen kann, wie zum Beispiel: Zyklen, fehlende Gewichte, negative Werte, zu viele Knoten, zu viele Kanten, zu wenige Knoten, zu wenige Kanten, etc...

Ich habe mein Code mehrmals durchgeschaut und alles nochmal überprüft, aber ich wüsste nicht, wo die Knoten mehr mals vorkommen könnten, die ich angeblich dann mehrfach ausgebe.

Hat jemand eine Idee, wie das gemeint sein könnte?

Verfasst: 15. Mai 2007 10:25
von HolgerF
Wird schon so gemeint sein, wie es da steht.
Wie das passieren kann:

War z. B. bei mir in meiner allerersten Fassung so, dass mein Zyklencheck beim BottomUp-Ansatz eine Möglichkeit übersehen hat und daher bei bestimmten Graphen die Zyklen nicht erkannt hat. Aufgrund meiner Implementierungsweise hab ich das sortierte Array mit der richtigen Größe vorab angelegt, und die Elemente darin waren alle anfangs 0. Nach der durchgeführten Sortierung sind dann wegen dem Zyklus nicht alle Elemente des Arrays geändert worden. Und so hatte ich dann z. B. mehrfach die 0 im Array stehen.

Ob das dann so einen Fehler im Testlauf generiert hätte, weiß ich nicht. Ich hab den Fehler schon vorm Einschicken gefunden...

Verfasst: 15. Mai 2007 10:31
von Abo
Naja, ich glaube nicht, dass bei mir das selbe wäre, weil nachdem ich einige Eigenschaften auf Exceptions etc... prüfe, dann suche ich den ersten Knoten, der keine eingehende Kante hat und füge ihn in einem Vektor und lösche dabei alle seine ausgehende Kanten zu allen anderen Nachbarn/Nachfolgern und deshalb ist es aus meiner Sicht unwahrscheinlich, dass der Knoten zweimal vorkommen kann, weil wegen seinem Nummer/ID er aus dem Graphen gelöscht wird, auch wenn zwischen zwei Kanten-Definitionen von diesem Knoten, noch andere Kanten-Definitionen von anderen Knoten stehen.

Das kommt mir aber merkwürdig vor.

Noch Ideen?

Verfasst: 15. Mai 2007 10:58
von HolgerF
Du kannst ja spaßeshalber mal einen solchen Graphen probieren:

1->2->3<-4 5->6->7->5

Der Witz ist, dass es für die zweite Hälfte keinen Eingangsknoten mit Grad 0 gibt. Ich jedenfalls hatte das zuerst vergessen, deswegen wurde die zweite Graphenhälfte gar nicht untersucht, also der Zyklus auch nicht entdeckt, und die zurückgegebene topologische Sortierung war dann Unfug.

Gut, im vorliegenden Test geht es wahrscheinlich nicht um illegale Eingaben, also enthält der betreffende Graph wohl eher keinen Zyklus. Im Zweifelsfall musst du halt einfach noch fleißig weitere Testcases basteln ;)
Ist deine Prüfung auf den gelöscht-Status eines Knotens vielleicht lückenhaft?

Verfasst: 15. Mai 2007 11:24
von 6(sic)6
Test 2 testet auf einen Graphen ohne Kanten, also das Testfile sieht zum Beispiel so aus.

5 0

Mehr nicht.

Verfasst: 15. Mai 2007 11:25
von Abo
Also in diesem Fall, wo ein Zyklus bei 5->6->7->5 vorkommt, wird dies von meinem Programm abgefangen. Deshalb wundere ich mich auch, wie der TestCase dafür aussehen sollte?!?!

Ich habe mehr Code zum Abfangen der Exceptions als für das Programm selbst.

Ich habe auch überlegt, ob dieser Fall es sein sollte:

1->2
2->3
3->4
1->3
3->5
1->5

Auch so ein Fall wird abgefangen. Also hier kommt zum Beispiel der Knoten 1 vor und danach andere Knoten und danach 1 wieder. Und dieser Fall wird auch abgefangen.

Hmmm..... mir fällt langsam nichts mehr ein, was es sein könnte.

Verfasst: 15. Mai 2007 11:26
von Panulli
ich habe bei dem 2. folgendes Problem;
Testsuite: Test_2
Tests run: 2, Failures: 0, Errors: 2, Time elapsed: 0.055 sec

Testcase: test_TopDown took 0.013 sec
Caused an ERROR
null
java.lang.NullPointerException
at java.util.StringTokenizer.<init>(StringTokenizer.java:197)
at java.util.StringTokenizer.<init>(StringTokenizer.java:234)
at TextReader.readFile(Unknown Source)
at Praktikum_3.getTopDown(Unknown Source)
at Test_2.test_TopDown(Unknown Source)

Testcase: test_BottomUp took 0.001 sec
Caused an ERROR
null
java.lang.NullPointerException
at java.util.StringTokenizer.<init>(StringTokenizer.java:197)
at java.util.StringTokenizer.<init>(StringTokenizer.java:234)
at TextReader.readFile(Unknown Source)
at Praktikum_3.getBottomUp(Unknown Source)
at Test_2.test_BottomUp(Unknown Source)

Habe dann eine exception eingebaut, die Prüft ob die Datei leer ist...allerdiongs mit einer GraphContainsCycle-Exception...daraufhin kam die Fehlermeldung das ich einen Zyklus finden würde wo keiner ist.
Das lässt darauf schließen, das Test2 eine leere Liste prüft?!?!?
Wobei ich mit einer IOException wieder den NullPointer-Fehler bekomme...prüfe das gerade mit einer FileFormatException.

Verfasst: 15. Mai 2007 11:27
von Abo
Hmmm... das ist ein interessanter Ansatz. Ich dachte, dass die Graphen so sind, wie in der Aufgabestellung. D.h. der Graph ist zusammenhängend.

Danke für den Tipp. Ich schaue, ob dieser Fall schon behandelt wird

Verfasst: 15. Mai 2007 11:35
von 6(sic)6
Wieso sollte er zusammenhängend sein? Auch ein nicht zusammenhängender Graph kann eine topologische Sortierung darstellen.

Wenn wir einen Graphen haben mit Knoten A, B, C. Mit nur einer Kante A->B

dann heißt das, dass A vor B kommen muss, der Rest kann beliebig sein. (Ich bitte um Korrektur falls das falsch ist) also wäre hier topologisch richtig:

ABC
CAB
ACB

PS: Kein Problem, ich helfe gerne wenn ich kann ;)

Verfasst: 15. Mai 2007 11:49
von 6(sic)6
Panulli hat geschrieben:ich habe bei dem 2. folgendes Problem;
Testsuite: Test_2
Tests run: 2, Failures: 0, Errors: 2, Time elapsed: 0.055 sec

Testcase: test_TopDown took 0.013 sec
Caused an ERROR
null
java.lang.NullPointerException
at java.util.StringTokenizer.<init>(StringTokenizer.java:197)
at java.util.StringTokenizer.<init>(StringTokenizer.java:234)
at TextReader.readFile(Unknown Source)
at Praktikum_3.getTopDown(Unknown Source)
at Test_2.test_TopDown(Unknown Source)

Testcase: test_BottomUp took 0.001 sec
Caused an ERROR
null
java.lang.NullPointerException
at java.util.StringTokenizer.<init>(StringTokenizer.java:197)
at java.util.StringTokenizer.<init>(StringTokenizer.java:234)
at TextReader.readFile(Unknown Source)
at Praktikum_3.getBottomUp(Unknown Source)
at Test_2.test_BottomUp(Unknown Source)

Habe dann eine exception eingebaut, die Prüft ob die Datei leer ist...allerdiongs mit einer GraphContainsCycle-Exception...daraufhin kam die Fehlermeldung das ich einen Zyklus finden würde wo keiner ist.
Das lässt darauf schließen, das Test2 eine leere Liste prüft?!?!?
Wobei ich mit einer IOException wieder den NullPointer-Fehler bekomme...prüfe das gerade mit einer FileFormatException.
Gehst du eventuell davon aus, dass nach der ersten Zeile auf jeden Fall noch eine zweite kommt? Falls ja, dann weißt du ja jetzt den Fehler. Wenn die Kantenanzahl 0 ist, kommt keine zweite Zeile mehr.... sollte zumindest nicht, wenn doch, dann auch das abfangen ;)

Verfasst: 15. Mai 2007 11:56
von Panulli
ich lesen einfach die erste Zeile ein...ist diese 'null' -> Fehler
dann die Zweite..gleiches Spiel
und dann mit einer Schleife den Rest...:-|

Verfasst: 15. Mai 2007 12:28
von Panulli
bekomme genau den Fehler zurück den ich werfen wenn die zweite Zeile 'null' ist....d.h. die eingabe ich scheinbar eine datei, die aus einer Zeile besteht...0 0...:-)

Verfasst: 15. Mai 2007 14:46
von MisterD123
0 0 wäre illegal weil knotenzahl >0 sein muss ;p

Verfasst: 15. Mai 2007 14:55
von Panulli
Mach mich nicht schwach...was sonst kann denn in einer Zeile stehen und gültig sein...:-|

Verfasst: 15. Mai 2007 15:48
von 6(sic)6
5 0 kann gültig sein, der Graph muss nicht zusammenhängen