Floydwarshall - complete

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!
LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Floydwarshall - complete

Beitrag von LukasPhysiker » 20. Jun 2017 22:33

Ich habe mal wieder einen Fall, wo ich bei den Teilaufgaben eines Algorithmus alle Tests bestehe und nur an der complete-Aufgabe scheitere. Hier ist mein Code:

Code: Alles auswählen

public boolean checkBreakCondition()
{
    return getIteration() < getGraph().getNodeList().size();
}

Code: Alles auswählen

public void executeVariant()
{
    setIteration(getIteration()+1);
    //currentNode = nodeQueue.remove();
}

Code: Alles auswählen

public void doFunctionality()
{
    int k = getMatrixIndex(getCurrentNode());
    int n = getGraph().getNodeList().size();
    AbstractEdgeComparator<E> comp = getGraph().getComparator();
    
    int v,w;
    
    for(v = 1; v<=n; v++ )
    {
        for(w = 1; w <= n; w++)
        {
            setM(v,w,comp.min(getM(v,w),comp.sum(getM(v,k),getM(k,w))));
        }
    }
}

Code: Alles auswählen

public void preProcess() throws InvalidInputException
{
    if(getGraph() == null) throw new InvalidInputException();
    if(getNodeQueue() == null) throw new InvalidInputException();
    if(!(getGraph().getNodeList().containsAll(getNodeQueue()) && getNodeQueue().containsAll((getGraph().getNodeList())))) throw new InvalidInputException();
    
    
    AbstractEdgeComparator<E> comp = getGraph().getComparator();
    
    setIteration(0);
    
    ArrayList<Node<N,E>> queue = getNodeQueue();
    
    int i,j,n=queue.size();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            setM(i,j,comp.getMax());
        }
        for(Edge<N,E> edge : queue.get(i-1).getFanOut())
        {
            setM(getMatrixIndex(queue.get(i-1)),getMatrixIndex(edge.getTargetNode()),edge.getData());
        }
        setM(i,i,comp.getZero());
    }
    
    setCurrentNode(queue.get(0));
}
Wie gesagt, alles bis auf preProcess() besteht die Tests in den Teilaufgaben, nur hier scheitert es wieder. Ich bestehe immerhin 9 / 11 Tests, nur zwei geben Fehlermeldungen:

Code: Alles auswählen

Antwort des Servers
Junitreport

    Time – 120

    Testcount – 11

    Failurecount – 2

    Ignorerecount – 0

Failurereport

    Testheadder – staticFunctionalityTestUndirectedGraphOne(graph.algorithm.FloydWarshallTest)

    Message – row: 1, col: 4 expected:<8> but was:<2147483647>

    Trace

Failurereport

    Testheadder – dynamicFullyConnectedSolutionTest(graph.algorithm.FloydWarshallTest)

    Message – Result of matrix M in row 1 and column 4 was supposed to be 2.372996 but was 2.932033. expected:<2.372995714696624> but was:<2.9320331529303645>

    Trace 
Das blöde an diesen Tests ist ja, dass sie zwar präzise sagen, wo ein Wert falsch ist, aber man sieht nicht den Graphen, also kann man am Ende doch nichts damit anfangen. Wieder einmal kann ich einfach durch meine Erfahrungen mit Codemonkeys nicht sicher sein, ob die Fehler bei Codemonkeys oder bei mir liegen...

Kann mir jemand helfen?

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

Re: Floydwarshall - complete

Beitrag von kommiker » 20. Jun 2017 23:10

Hallo Lukas,

ich kann dir leider nicht konkret sagen wo der Fehler ist, aber mir ist etwas aufgefallen. Dein executeVariant() besteht zwar alle Tests, ich bin mir aber nicht sicher ob es das sollte. Ich meine du veränderst den currentNode nicht und das sollte laut Aufgabe gemacht werden.

lg kommiker

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

Re: Floydwarshall - complete

Beitrag von LukasPhysiker » 21. Jun 2017 18:58

Ah, stimmt, ich habe ja, wie du in meinem Code siehst, erst versucht, currentNode auf das nächste Element in der nodeQueue zu setzen, aber dabei schlagen die Tests fehl:

Code: Alles auswählen

Antwort des Servers
Consistencyreport
Function call detection:
Function call detection:

    forbidden call to method: – remove
Das selbe mit poll(); Es scheint also so, als ob die entsprechende Methode nicht gewhitelistet wäre. Ich habe damals die Zeile auskommentiert und erstmal vergessen, dass da eigentlich mal wieder ein Bug ist - außer es gibt eine andere vorgesehene Möglichkeit, das nächste Element zu bekommen.

Ich bitte also darum, dass dieser Bug gefixt wird.

Kabooom
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: Floydwarshall - complete

Beitrag von Kabooom » 21. Jun 2017 20:18

Hallo Lukas,

der Trick ist, dass die nodeQueue in Wirklichkeit keine queue ist sondern eine ArrayList (warum auch immer). Das heißt, dass man anscheinend in jeder Iteration getNodeQueue().get(getIteration()) in der currentNode abspeichern soll, falls checkBreakCondition() true ist (Ich weiß auch nicht, warum in der Variante nochmal die breakCondition überprüft wird, es ist aber so gefordert).

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

Re: Floydwarshall - complete

Beitrag von LukasPhysiker » 21. Jun 2017 20:29

Hallo Kaboom,

danke für deinen Hinweis, aber ich bekomme das immer noch nicht zum Laufen. Das ist jetzt mein Code:

Code: Alles auswählen

public void executeVariant()
{
    setIteration(getIteration()+1);
    if(checkBreakCondition) currentNode = getNodeQueue().get(getIteration());
}
Und das ist die Antwort des Servers:

Code: Alles auswählen

Antwort des Servers
Consistencyreport
Function call detection:
Function call detection:

    forbidden call to method: – get
get ist also wohl auch nicht gewhitelistet. In jedem Fall, wenn das stimmt, was du sagst, dass das eine ArrayList ist, dann wäre das einfacher zu sehen, wenn getNodeQueue() in der Aufgabe beschrieben worden wäre...

Kabooom
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: Floydwarshall - complete

Beitrag von Kabooom » 21. Jun 2017 20:32

Hallo Lukas,

du kannst soweit ich weiß nicht direkt auf das Feld currentNode zugreifen, stattdessen solltest du setCurrentNode() verwenden.

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

Re: Floydwarshall - complete

Beitrag von LukasPhysiker » 21. Jun 2017 20:40

Ok, das war bei den Graph-Algorithmen nie konsequent so; meistens konnte ich direkt auf die Datenfelder zugreifen. Ich habe jetzt also setCurrentNode() benutzt, dann habe ich festgestellt, dass ich bei checkBreakCondition das () vergessen hatte und statt getIteration() muss man getIteration()-1 einsetzen. Dan funktioniert zumindest wieder der Test für checkBreakCondition/executeVariant. Danke schonmal dafür. Das ist jetzt mein Code:

Code: Alles auswählen

public void executeVariant()
{
    setIteration(getIteration()+1);
    if(checkBreakCondition()) setCurrentNode(getGraph().getNodeList().get(getIteration()-1));
}
Im complete-Test bekomme ich aber immer noch eine Fehlermeldung:

Code: Alles auswählen

Antwort des Servers
Junitreport

    Time – 141

    Testcount – 11

    Failurecount – 1

    Ignorerecount – 0

Failurereport

    Testheadder – dynamicFullyConnectedSolutionTest(graph.algorithm.FloydWarshallTest)

    Message – Result of matrix M in row 1 and column 4 was supposed to be 2.372996 but was 2.932033. expected:<2.372995714696624> but was:<2.9320331529303645>

    Trace 
Am Anfang waren es zwei Fehlermeldungen, jetzt ist es nur noch eine. Das ist schonmal ein Fortschritt. Ich frage mich nur, wo der letzte Fehler jetzt herkommt...

Kabooom
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: Floydwarshall - complete

Beitrag von Kabooom » 21. Jun 2017 20:49

Ich glaube du solltest dir die node aber nicht aus getNodeList sondern aus getNodeQueue holen, dann funktioniert es auch mit getIteration ohne minus 1. Außerdem ist es für den Algorithmus wichtig, dass die Knoten in der Reihenfolge abgearbeitet werden, wie sie in der nodeQueue sind, nicht in der nodeList des Graphen.

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

Re: Floydwarshall - complete

Beitrag von LukasPhysiker » 21. Jun 2017 20:59

Ah richtig, sorry, das habe ich beim Experimentieren geändert und nicht zurückgeändert. Das ist jetzt meine executeVariant():

Code: Alles auswählen

public void executeVariant()
{
    setIteration(getIteration()+1);
    if(checkBreakCondition()) setCurrentNode(getNodeQueue().get(getIteration()));
}
Wieder genau ein Fehler:

Code: Alles auswählen

Antwort des Servers
Junitreport

    Time – 109

    Testcount – 11

    Failurecount – 1

    Ignorerecount – 0

Failurereport

    Testheadder – dynamicFullyConnectedSolutionTest(graph.algorithm.FloydWarshallTest)

    Message – Result of matrix M in row 1 and column 4 was supposed to be 2.372996 but was 2.932033. expected:<2.372995714696624> but was:<2.9320331529303645>

    Trace 

Antworten

Zurück zu „AuD: Programmieraufgaben“