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

[kommiker]

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]

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

lg kommiker

[kommiker]

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]

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]

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

lg kommiker

[Vykyfikation]

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]

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

lg kommiker

[OAEP]

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

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

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]

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]

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