Dijkstra: invariant It seems like the method default throws the exception

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Dijkstra: invariant It seems like the method default throws the exception

Beitrag von kommiker » 29. Mai 2017 13:22

Hallo,
ich finde leider im Folgenden meinen Fehler nicht:

Code: Alles auswählen

public void checkInvariant() throws InvalidInvariantException{

		//Check if source node is in PrioQueue
		if(getPriorityQueue().contains(getSourceNode())){
			throw new InvalidInvariantException("source node isnt allowed to be in prio queue");
		}

		//Check if all setteld nodes have distance != inf
		for(Node<N, E> n: getSettled()){
			if(getComparator().compare(getDistances().get(n), getComparator().getMax())==0){
				throw new InvalidInvariantException("settled nodes shouldn't have distance inf"); 
			}
		}

		//every unsettled node, which is not in prioqueue, should have distance max
		for(Node<N, E> n: getGraph().getNodeList()){
			if(getSettled().contains(n)==false){
				if(getPriorityQueue().contains(n)==false){
					if(getComparator().compare(getDistances().get(n),getComparator().getMax())!=0){
						throw new InvalidInvariantException("unsettled nodes should have distance max if no in prioqueue");
					}
				}
			}
		}

		//check, if the amount of iterations equals the amount of setteld nodes
		if(getIterations() != getSettled().size()){
			throw new InvalidInvariantException("the amount of iterations should equal the amount of settled nodes");
		}
	}
Die Fehlermeldung:
It seems like the method default throws the exception
Ich bin eigentlich der Meinung das ich die Spezifikation erfülle und alles funktionieren sollte.

Code: Alles auswählen

		//Check if source node is in PrioQueue
		if(getPriorityQueue().contains(getSourceNode())){
			throw new InvalidInvariantException("source node isnt allowed to be in prio queue");
		}
Hier schaue ich einfach ob der Startknoten in der PrioQueue ist, falls er das ist, wird eine Exception geworfen. (Erfüllt Punkt 1 der Spezifikation)

Code: Alles auswählen

		//Check if all setteld nodes have distance != inf
		for(Node<N, E> n: getSettled()){
			if(getComparator().compare(getDistances().get(n), getComparator().getMax())==0){
				throw new InvalidInvariantException("settled nodes shouldn't have distance inf"); 
			}
		}
Hier wird für jeden Knoten, welcher vom Algorithmus verarbeitet wurde geschaut, ob seine Distanz zum Startknoten gleich der Max Distanz ist, wenn ja, dann wird die Exception geworfen.

Code: Alles auswählen

		//every unsettled node, which is not in prioqueue, should have distance max
		for(Node<N, E> n: getGraph().getNodeList()){
			if(getSettled().contains(n)==false){
				if(getPriorityQueue().contains(n)==false){
					if(getComparator().compare(getDistances().get(n),getComparator().getMax())!=0){
						throw new InvalidInvariantException("unsettled nodes should have distance max if no in prioqueue");
					}
				}
			}
		}
Hier wird die Liste aller Knoten travasiert. Es wird für jeden Knoten geschaut, ob er noch nicht abgearbeitet ist und nicht in der PrioQueue. Falls das der Fall ist, dann muss nach Spezifikation die Distanz Max sein. Dies wird dann auch einfach per if im Folgenden abgefragt und ggf. die Exception geworfen.

Code: Alles auswählen

		//check, if the amount of iterations equals the amount of setteld nodes
		if(getIterations() != getSettled().size()){
			throw new InvalidInvariantException("the amount of iterations should equal the amount of settled nodes");
		}
Hier wird einfach der letzte Punkt der Spezifikation überprüft. Man schaut per if ob die Anzahl der Iterationen gleich der Anzahl der abgearbeiteten Knoten ist.

Wie bereits gesagt, ich konnte meinen Fehler leider nicht finden und würde mich sehr freuen, falls jemandem etwas auffällt.

Ich hoffe ich konnte meinen Code gut erläutern und würde mich sehr über Antwort und Hilfe freuen.

Liebe Grüße
kommiker

kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von kommiker » 31. Mai 2017 17:24

Hänge leider immernoch am selben Problem. Hat jemand, Student oder Lehrveranwortlicher, einen Lösung/Tipp für mich?

lg kommiker

kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von kommiker » 2. Jun 2017 15:39

Ich habe hier ein inhaltliches Problem und suche wirklich Hilfe?! Normalerweise benötige ich keine Musterlösung wenn die Möglichkeit besteht inhaltliche Frage zuklären. Dies ist hier definitiv nicht der Fall, denn es gibt keine Sprechstunden zu Codemonkey und im Forum wird auf Fragen, wenn überhaupt, nur sehr unkontinuierlich geantwortet. D.h wenn man an einem Problem nicht weiter kommt und einem die Kommilitonen nicht weiterhelfen können, dann steht man alleine da.
Ich finde dies sehr bedauerlich, weil ich sehr viel Zeit in Codemonkey (und seine Bugs und deren Report!) investiert habe.

lg
kommiker

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von invariant » 2. Jun 2017 18:57

Hallo,

leider kann ich Ihnen an dieser Stelle nicht weiterhelfen. Allerdings gibt es Sprechstunden bzgl. Java

ab 19.Mai wöchentlich freitagszwischen 11:40 bis 15:10 in S2|02 C003 - Java Sprechstunden bei Harun Polat
https://moodle.informatik.tu-darmstadt. ... hp?id=7255

Gruß

kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von kommiker » 2. Jun 2017 20:34

Danke für die Antwort. Ich werde die Sprechstunde aufsuchen.

lg kommiker

Vykyfikation
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 9. Mai 2017 12:44

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von Vykyfikation » 6. Jun 2017 13:57

Den gleichen Fehler hatte ich auch. Du musst die 4. Abfrage vor der 3. machen, dann funktioniert der Code. Hier meine Lösung:

Code: Alles auswählen

{
    PriorityQueue<Node<N, E>> pri = getPriorityQueue();
    Node<N, E> nod = getSourceNode();
    if (pri.contains(nod))
        throw new InvalidInvariantException("blab");
    HashSet<Node<N, E>> set = getSettled();
    HashMap<Node<N, E>, E> dis = getDistances();
    for (Node s : set) {
            if (getComparator().compare(dis.get(s),getComparator().getMax())==0) {
                throw new InvalidInvariantException("blab");
            }
    }
    if(set.size() != getIterations()) throw new InvalidInvariantException("blab");
    for(Node d: dis.keySet()){
        if(!set.contains(d) && getComparator().compare(dis.get(d),getComparator().getMax())!=0){
            throw new InvalidInvariantException("blab");
        }
    }
}

kommiker
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:25

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von kommiker » 6. Jun 2017 19:18

Wow :D Tatsächlich klappt das. Aber wieso? Das sollte doch rein theoretisch keinen Unterschied machen oder? Trotzdem vielen vielen Dank!!

lg kommiker

OAEP
Neuling
Neuling
Beiträge: 4
Registriert: 31. Mai 2017 15:50

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von OAEP » 13. Jun 2017 17:48

Dieser Code wird abgelehnt:

Code: Alles auswählen

    AbstractEdgeComparator<E> comp = getComparator();
    E MAX = comp.getMax();
    
    PriorityQueue<Node<N,E>> queue = getPriorityQueue();
    Node<N,E> start = getSourceNode();
    if (queue.contains(start)) throw new InvalidInvariantException("");
    
    HashSet<Node<N,E>> settled = getSettled();
    HashMap<Node<N,E>, E> distances = getDistances();

    for (Node<N,E> n : getGraph().getNodeList()) {
        if (settled.contains(n)) {
            if (comp.compare(MAX, distances.get(n)) != -1)
                throw new InvalidInvariantException("");
        } else {
            if (!queue.contains(n))
                if (comp.compare(MAX, distances.get(n)) == 1)
                    throw new InvalidInvariantException("");
        }
    }
    
    if (getIterations() != settled.size()) throw new InvalidInvariantException("");
Dieser hier funktioniert:

Code: Alles auswählen

    AbstractEdgeComparator<E> comp = getComparator();
    E MAX = comp.getMax();
    
    PriorityQueue<Node<N,E>> queue = getPriorityQueue();
    Node<N,E> start = getSourceNode();
    if (queue.contains(start)) throw new InvalidInvariantException("");
    
    HashSet<Node<N,E>> settled = getSettled();
    HashMap<Node<N,E>, E> distances = getDistances();
    
    if (getIterations() != settled.size()) throw new InvalidInvariantException("");

    for (Node<N,E> n : getGraph().getNodeList()) {
        if (settled.contains(n)) {
            if (comp.compare(MAX, distances.get(n)) != -1)
                throw new InvalidInvariantException("");
        } else {
            if (!queue.contains(n))
                if (comp.compare(MAX, distances.get(n)) == 1)
                    throw new InvalidInvariantException("");
        }
    }
Ihr könnt euch das genau durchlesen sparen: Bei ersterem wird getIterations() != settled.size() am Ende ausgeführt. Bei zweiterem bevor die Logik zu den Distanzen geprüft wird. Aber, jetzt kommt das beste: Wenn man es noch weiter zum Anfang (vor dem Aufruf von getSettled und getDistances) schiebt, dann failts wieder :lol:

"It seems like the method default throws the exception"
Ne, it seems like Codemonkeys is totally broken :D

Spaß beiseite, man muss sich zum derzeitigen Zustand von Codemonkeys eher auf das Testat vorbereiten, um auf die Bugs gefasst zu sein, als zu Übungszwecken...

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von LukasPhysiker » 15. Jun 2017 21:21

Danke, wegen diesem Fehler habe ich auch lange herumgerätselt!

Falls es wen interessiert, ich habe die Abrage bezüglich der priorityQueue und der settled-Liste einzeln gemacht und es ist anscheinend nur wichtig, dass die priorityQueue nach der settled.size() Abfrage kommt und die Abfrage ob der sourceNode in der priorityQueue davor. Dieser Code funktioniert zum Beispiel:

Code: Alles auswählen

public void checkInvariant() throws InvalidInvariantException
{
    // die PriorityQueue enthält nicht den Startknoten
    if(getPriorityQueue().contains(getSourceNode())) throw new InvalidInvariantException();
    
    AbstractEdgeComparator<E> comp = getComparator();
    HashMap<Node<N,E>,E> distances = getDistances();
    HashSet<Node<N, E>> settled = getSettled();
    PriorityQueue<Node<N, E>> priorityQueue = getPriorityQueue();
    
    
    
    // für jeden abgearbeiteten Knoten ist die Distanz ungleich MAX_VALUE
    for(Node<N,E> node : settled)
    {
        if(comp.compare(distances.get(node),comp.getMax()) >= 0) throw new InvalidInvariantException();
    }
    
    ArrayList<Node<N, E>> nodeList = getGraph().getNodeList();
    
    
    // nach jeder Iteration i sind i Knoten abgearbeitet
    if(settled.size() != getIterations())  throw new InvalidInvariantException();
    
    
    // jeder unbesuchte Knoten, welcher nicht in der PriorityQueue enthalten ist, hat eine Distanz von MAX_VALUE 
    for(Node<N,E> node : nodeList)
    {
        if(!priorityQueue.contains(node))
        {
            if(comp.compare(distances.get(node),comp.getMax()) != 0) throw new InvalidInvariantException();
        }
    }
}

Das schlimmste an der Sache ist ja, dass die Reihenfolge in der Aufgabenstellung willkürlich hätte gewählt werden können aber sie wurde genau so gewählt, dass es nicht funktioniert. Man sollte meinen, dass das die gleiche Reihenfolge wäre wie in der Musterlösung und dann hätte es den Authoren Marcel Beuth und Tristan Wirth ja auffallen sollen.

Ich habe auch gerade meinen Testattermin um eine Woche nach hinten verschoben. Durch die vielen Bugs dauert die Vorbereitung bei mir jetzt viel länger als erwartet. Wie OAEP richtig sagt, es geht am Ende nicht darum, den Algorithmus zu verstehen, sondern die Bugs zu verstehen und umgehen zu können. Genauso wie es bei den Nabla-Testaten auch nicht darum ging, die Algorithmen zu verstehen, sondern zu lernen in welchen Tests die Indizes mit 1 oder 0 anfangen und was als "Iteration" zählt und teilweise einfach zu üben von Hand eine Zahl modulo 17 zu nehmen...

Vykyfikation
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 9. Mai 2017 12:44

Re: Dijkstra: invariant It seems like the method default throws the exception

Beitrag von Vykyfikation » 21. Jun 2017 12:57

Das ist ja echt gemein, kann ein Admin die Tests bitte mal ändern? :O

Antworten

Zurück zu „AuD: Programmieraufgaben“