Δομές Δεδομένων - Εργασία 3 [2016-17]

[James]

Εδώ μπορείτε να υποβάλετε ερωτήσεις, απορίες ή παρατηρήσεις σχετικές με την 3η εργασία, η οποία θα υποβληθεί μέσω του συστήματος Moodle.

[Oblimo]

Για τον αλγόριθμο Dijkstra:
Ο κωδίκας που έχω γράψει, βγάζει failure σε 16 τεστ ενώ σε όλα τα άλλα δεν ύπαρχει πρόβλημα. π.χ στο τεστ 4

Κώδικας: Επιλογή όλων

java.lang.AssertionError: Invalid distance(s) (error margin of 1.0E-4) from start node 2 in graph:|V| = 5, |E| = 9, E = {
0->2=5.0,
0->4=3.0,
1->3=3.0,
2->3=1.0,
2->4=4.0,
3->1=2.0,
3->4=2.0,
4->1=1.0,
4->3=5.0,
}
 expected :<[Infinity, 3.0, 0.0, 1.0, 3.0]> but was:<[9999.0, 3.0, 0.0, 1.0, 3.0]>
   at org.junit.Assert.fail(Assert.java:88)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.forceFailEquals(Helpers.java:130)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.doubleArrayEquals(Helpers.java:89)
   at gr.duth.ee.euclid.datastructures.testing_framework.project_specific.TestCaseTester.test(TestCaseTester.java:45)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.ParametrizedTest.test(ParametrizedTest.java:67)
   at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
   at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
   at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
   at java.lang.reflect.Method.invoke(Method.java:498)
   at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:47)
   at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
   at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:44)
   at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
   at org.junit.internal.runners.statements.FailOnTimeout$StatementThread.run(FailOnTimeout.java:74)

Από ότι φαίνεται ο πίνακας που επιστρέφω είναι σώστος. Που μπόρει να οφείλεται το failure;

[mpampis]

Το startNode του αλγοριθμου ποιο θα θεωρειται?

[James]

Για τον αλγόριθμο Dijkstra:
Ο κωδίκας που έχω γράψει, βγάζει failure σε 16 τεστ ενώ σε όλα τα άλλα δεν ύπαρχει πρόβλημα. π.χ στο τεστ 4

Κώδικας: Επιλογή όλων

java.lang.AssertionError: Invalid distance(s) (error margin of 1.0E-4) from start node 2 in graph:|V| = 5, |E| = 9, E = {
0->2=5.0,
0->4=3.0,
1->3=3.0,
2->3=1.0,
2->4=4.0,
3->1=2.0,
3->4=2.0,
4->1=1.0,
4->3=5.0,
}
 expected :<[Infinity, 3.0, 0.0, 1.0, 3.0]> but was:<[9999.0, 3.0, 0.0, 1.0, 3.0]>
   at org.junit.Assert.fail(Assert.java:88)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.forceFailEquals(Helpers.java:130)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.doubleArrayEquals(Helpers.java:89)
   at gr.duth.ee.euclid.datastructures.testing_framework.project_specific.TestCaseTester.test(TestCaseTester.java:45)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.ParametrizedTest.test(ParametrizedTest.java:67)
   at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
   at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
   at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
   at java.lang.reflect.Method.invoke(Method.java:498)
   at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:47)
   at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
   at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:44)
   at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
   at org.junit.internal.runners.statements.FailOnTimeout$StatementThread.run(FailOnTimeout.java:74)

Από ότι φαίνεται ο πίνακας που επιστρέφω είναι σώστος. Που μπόρει να οφείλεται το failure;

Ο πίνακας που επιστρέφεις είναι λάθος όπως φαίνεται και από το μήνυμα του test. Πράγματι, ο αριθμός 9999.0 είναι τελείως αυθαίρετος και θα έπρεπε να είναι άπειρο η συγκεκριμένη θέση (δηλαδή δεν χρειάζεται να την αλλάξεις) αφού ο κόμβος 0 (μηδέν) δεν έχει εισερχόμενες ακμές.

[James]

Το startNode του αλγοριθμου ποιο θα θεωρειται?

Το startNode είναι παράμετρος του αλγορίθμου και η τιμή της βρίσκεται στο ομώνυμο πεδίο του class. Θα πρέπει να χρησιμοποιήσετε την τιμή αυτή στην υλοποίηση του αλγορίθμου.

[mpampis]

Δοκιμαστικα πως μπορουμε να τρεξουμε τον αλγοριθμο μας ?

[Oblimo]

Ποιά είναι η τιμή του Infinity ?

[James]

Δοκιμαστικα πως μπορουμε να τρεξουμε τον αλγοριθμο μας ?

Η διαδικασία εκτέλεσης των tests που δείξαμε στο φροντιστήριο αποτελεί έναν τρόπο να δοκιμάσετε την υλοποίησή σας. Αυτή η διαδικασία περιγράφεται στις σημειώσεις (scribes) της πρώτης εργασίας (Run As JUnit Test στο project-testing.jar). Δεν είμαι σίγουρος αν ρωτάς κάτι περισσότερο από αυτό.

[James]

Ποιά είναι η τιμή του Infinity ?

Μπορείς να δεις στην περιγραφή της ερώτησης (σε πολλαπλά σημεία εντός αυτής) στον κατάλογο description την τιμή αυτή που είναι Double.POSITIVE_INFINITY και πώς χρησιμοποιείται.

[mpampis]

Υπαρχει περιπτωση το graph-MST να μην ειναι μοναδικο ?
Τον αλγοριθμο Kruskal να χρησιμοποιουμε ?

[James]

Υπαρχει περιπτωση το graph-MST να μην ειναι μοναδικο ?
Τον αλγοριθμο Kruskal να χρησιμοποιουμε ?

Τα γραφήματα που έχετε στη διάθεσή σας για τα test είναι έτσι φτιαγμένα που δεν υπάρχει περίπτωση να μην είναι μοναδική η απάντηση. Για κάθε γράφημα υπάρχει μόνο ένα MST. Μπορείτε να χρησιμοποιήσετε όποιον αλγόριθμο θέλετε από αυτούς που διδαχτήκατε για την υλοποίηση του MST (Prim, Kruskal, Reverse-Delete).

[alliceinw0]

Ποια είναι η σημασία του nodeThrough; Στο description toy Dijkstra γιατί το nodeThrough είναι 2 και για τον κόμβο 2 που είναι ο starting node και για τον κόμβο 3;

[James]

Ποια είναι η σημασία του nodeThrough; Στο description toy Dijkstra γιατί το nodeThrough είναι 2 και για τον κόμβο 2 που είναι ο starting node και για τον κόμβο 3;

Ο πίνακας nodeThrough (πρέπει να) έχει αποθηκευμένους τους κόμβους μέσω των οποίων επιτυχγάνονται οι προηγούμενες αποστάσεις.

Για τον κόμβο 3 το nodeThrough είναι 2 επειδή το συντομότερο μονοπάτι από τον 2 προς τον 3 είναι το 2 -> 3 (με βάρος 1) και ο προηγούμενος από τον 3, δηλαδή αυτός ο κόμβος μέσω του οποίου φτάνει κανείς στον 3, είναι ο 2. Επιπλέον, δες αυτή την απάντηση καθώς και το αρχείο Closeness.pdf που έχει παράδειγμα για το nodeThrough (που δείξαμε στο φροντιστήριο).

Η έννοια του nodeThrough έχει να κάνει με τον αλγόριθμο τον ίδιο και δεν είναι κάποια ιδιαιτερότητα της εργασίας. Για παράδειγμα δες στη σελίδα 38 των διαφανειών της θεωρίας του μαθήματος. Η τιμή nodeThrough είναι το δεύτερο αντικείμενο του ζευγαριού (x,y) που υπάρχει σε κάτι θέση του πίνακα.

[alliceinw0]

Ευχαριστώ πολύ! Θα ήθελα να ρωτήσω και κάτι ακόμα... Μέσα στην κλάση Mst μπορούμε να υλοποιήσουμε και δικές μας επιπλέον συναρτήσεις;

[georgev]

Η μέθοδος existsEdge(int i, int j) μας δίνει το αν η ακμή υπάρχει ή αν η ακμή υπάρχει και είναι και εξερχόμενη από τον κόμβο i;