Astern - functionality

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

Astern - functionality

Beitrag von LukasPhysiker » 21. Jun 2017 20:24

Ich bekomme Nullpointerexceptions in Comparator.sum, obwohl ich extra nochmal sichergehe, dass die Argumente nicht null sind...

Hier ist mein Code:

Code: Alles auswählen

public void doFunctionality()
{
    Node<N,E> currentNode = getCurrentNode();
    
    if(currentNode == null || currentNode == getTargetNode()) setPathFound(true);
    else
    {
        getClosedList().add(currentNode);
        expandNode(currentNode);
    }
}

Code: Alles auswählen

private void expandNode(Node<N, E> node)
{
    if(node == null) return;
    
    AbstractEdgeComparator<E> comp = getComparator();
    
    PriorityQueue<Node<N, E>> openList = getOpenList();
    Node<N,E> targetNode;
    for(Edge<N,E> edge : node.getFanOut())
    {
        targetNode = edge.getTargetNode();
        openList.offer(targetNode);
        if(sourceDistanceMap.get(targetNode) == null)
        {
            if(sourceDistanceMap.get(node) != null && edge.getData() != null)
            {
                sourceDistanceMap.put(targetNode,comp.sum(sourceDistanceMap.get(node),edge.getData()));
                predecessorMap.put(targetNode,node);
            }
            
        }
        else
        {
            if(comp.compare(sourceDistanceMap.get(targetNode),comp.sum(sourceDistanceMap.get(node),edge.getData())) > 0)
            {
                if(sourceDistanceMap.get(node) != null && edge.getData() != null)
                {
                    sourceDistanceMap.put(targetNode,comp.sum(sourceDistanceMap.get(node),edge.getData()));
                    predecessorMap.put(targetNode,node);
                }
                
            }
        }
        
    }
}
Die Antwort des Servers mit expandierten Traces:

Code: Alles auswählen

Antwort des Servers
Junitreport

    Time – 27

    Testcount – 5

    Failurecount – 2

    Ignorerecount – 0

Failurereport

    Testheadder – staticFunctionTest(graph.algorithm.astar.AStarFunctionalityTest)

    Message –

    Trace – java.lang.NullPointerException at models.graph.data.DoubleDataComparator.sum(DoubleDataComparator.java:11) at models.graph.data.DoubleDataComparator.sum(DoubleDataComparator.java:6) at graph.algorithm.astar.AStar.getDistWithHeuristic(AStar.java:272) at graph.algorithm.astar.AStar.lambda$getQueueComparator$0(AStar.java:416) at java.util.PriorityQueue.siftUpUsingComparator(PriorityQueue.java:669) at java.util.PriorityQueue.siftUp(PriorityQueue.java:645) at java.util.PriorityQueue.offer(PriorityQueue.java:344) at wrap.substitute.PriorityQueue.offer(PriorityQueue.java:80) at graph.algorithm.astar.AStar.expandNode(AStar.java:215) at graph.algorithm.astar.AStar.doFunctionality(AStar.java:182) at models.graph.algorithm.AbstractAlgorithm.execute(AbstractAlgorithm.java:26) at graph.algorithm.astar.AStarFunctionalityTest.staticFunctionTest(AStarFunctionalityTest.java:147) 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:50) at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12) at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47) at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:298) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:292) at java.util.concurrent.FutureTask.run(FutureTask.java:266) at java.lang.Thread.run(Thread.java:745)

Failurereport

    Testheadder – dynamicFunctionTestNotConnected(graph.algorithm.astar.AStarFunctionalityTest)

    Message –

    Trace – java.lang.NullPointerException at models.graph.data.DoubleDataComparator.sum(DoubleDataComparator.java:11) at models.graph.data.DoubleDataComparator.sum(DoubleDataComparator.java:6) at graph.algorithm.astar.AStar.getDistWithHeuristic(AStar.java:272) at graph.algorithm.astar.AStar.lambda$getQueueComparator$0(AStar.java:416) at java.util.PriorityQueue.siftUpUsingComparator(PriorityQueue.java:669) at java.util.PriorityQueue.siftUp(PriorityQueue.java:645) at java.util.PriorityQueue.offer(PriorityQueue.java:344) at wrap.substitute.PriorityQueue.offer(PriorityQueue.java:80) at graph.algorithm.astar.AStar.expandNode(AStar.java:215) at graph.algorithm.astar.AStar.doFunctionality(AStar.java:182) at models.graph.algorithm.AbstractAlgorithm.execute(AbstractAlgorithm.java:26) at graph.algorithm.astar.AStarFunctionalityTest.dynamicFunctionTestNotConnected(AStarFunctionalityTest.java:189) 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:50) at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12) at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47) at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:298) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:292) at java.util.concurrent.FutureTask.run(FutureTask.java:266) at java.lang.Thread.run(Thread.java:745)
Weiß jemand woran das liegen kann?

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: Astern - functionality

Beitrag von joshimoo » 21. Jun 2017 22:03

Hallo Lukas,

hab mir den Code jetzt nicht genau angesehen, mir ist nur aufgefallen.
Das du im else fall nicht pruefst ob es null ist:

Code: Alles auswählen

//...
        else
        {
            if(comp.compare(sourceDistanceMap.get(targetNode),comp.sum(sourceDistanceMap.get(node),edge.getData())) > 0)
            {
//...

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

Re: Astern - functionality

Beitrag von LukasPhysiker » 21. Jun 2017 22:19

Hallo joshimoo,

danke für den Hinweis! Ich habe das jetzt korrigiert, aber ich habe immer noch die gleichen Fehler. Jedenfalls ist das jetzt mein aktueller Code:

Code: Alles auswählen

{
    if(node == null) return;
    
    AbstractEdgeComparator<E> comp = getComparator();
    
    PriorityQueue<Node<N, E>> openList = getOpenList();
    Node<N,E> targetNode;
    for(Edge<N,E> edge : node.getFanOut())
    {
        targetNode = edge.getTargetNode();
        openList.offer(targetNode);
        if(sourceDistanceMap.get(targetNode) == null)
        {
            if(sourceDistanceMap.get(node) != null && edge.getData() != null)
            {
                sourceDistanceMap.put(targetNode,comp.sum(sourceDistanceMap.get(node),edge.getData()));
                predecessorMap.put(targetNode,node);
            }
            
        }
        else
        {
            if(sourceDistanceMap.get(targetNode) != null && edge.getData() != null)
            {
                if(comp.compare(sourceDistanceMap.get(targetNode),comp.sum(sourceDistanceMap.get(node),edge.getData())) > 0)
                {
                    sourceDistanceMap.put(targetNode,comp.sum(sourceDistanceMap.get(node),edge.getData()));
                    predecessorMap.put(targetNode,node);
                }
                
            }
        }
        
    }
}

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: Astern - functionality

Beitrag von joshimoo » 21. Jun 2017 23:18

Code: Alles auswählen

        if(sourceDistanceMap.get(targetNode) == null)
        {
//...
        else
        {
            if(sourceDistanceMap.get(targetNode) != null && edge.getData() != null)
            {
                if(comp.compare(sourceDistanceMap.get(targetNode),comp.sum([b]sourceDistanceMap.get(node)[/b],edge.getData())) > 0)
//...
Mir faellt auf das du:
- Du pruefst im else fall auf targetNode != null was ja laut deinem code sowieso immer erfuellt ist.
- Dann machst du allerdings den comp.sum auf der node

Wuerde empfehlen das du dir den Algorithmus nochmal im Wiki anschaust :)

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

Re: Astern - functionality

Beitrag von LukasPhysiker » 22. Jun 2017 19:55

Ok, das mit targetNode != null war in der Tat redundant. Ich wollte nach den NullPointerExceptions einfach sichergehen, dass keine Null-Pointer in den Comparator gefüttert werden und habe nicht darauf geachtet, was sowieso nicht null sein kann.

Nach deinem Hinweis mit dem Wiki habe ich mich jetzt mal ganz stumpf an den Pseudocode gehalten, den ich im Wiki gefunden habe:

Code: Alles auswählen

// überprüft alle Nachfolgeknoten und fügt sie der Open List hinzu, wenn entweder
// - der Nachfolgeknoten zum ersten Mal gefunden wird oder
// - ein besserer Weg zu diesem Knoten gefunden wird
function expandNode(currentNode)
    foreach successor of currentNode
        // wenn der Nachfolgeknoten bereits auf der Closed List ist – tue nichts
        if closedlist.contains(successor) then
            continue
        // g-Wert für den neuen Weg berechnen: g-Wert des Vorgängers plus
        // die Kosten der gerade benutzten Kante
        tentative_g = g(currentNode) + c(currentNode, successor)
        // wenn der Nachfolgeknoten bereits auf der Open List ist,
        // aber der neue Weg nicht besser ist als der alte – tue nichts
        if openlist.contains(successor) and tentative_g >= g(successor) then
            continue
        // Vorgängerzeiger setzen und g Wert merken
        successor.predecessor := currentNode
        g(successor) = tentative_g
        // f-Wert des Knotens in der Open List aktualisieren
        // bzw. Knoten mit f-Wert in die Open List einfügen
        f := tentative_g + h(successor)
        if openlist.contains(successor) then
            openlist.decreaseKey(successor, f)
        else
            openlist.enqueue(successor, f)
    end
end
Mein Code sieht jetzt so aus:

Code: Alles auswählen

private void expandNode(Node<N, E> node)
{
    if(node == null) return;
    
    AbstractEdgeComparator<E> comp = getComparator();
    
    PriorityQueue<Node<N, E>> openList = getOpenList();
    Node<N,E> targetNode;
    for(Edge<N,E> edge : node.getFanOut())
    {
        targetNode = edge.getTargetNode();
        if(closedList.contains(targetNode)) continue;
        
        E tentative_g = comp.sum(sourceDistanceMap.get(node),edge.getData());
        
        if(openList.contains(targetNode) && comp.compare(tentative_g,sourceDistanceMap.get(targetNode)) > 0)
        {
            continue;
        }
        
        predecessorMap.put(targetNode,node);
        sourceDistanceMap.put(targetNode,tentative_g);
        
        openList.add(targetNode);
    }
}
Und jetzt bestehe ich alle Tests! Danke für den Hinweis! :D
Ich dachte erst, es wäre so viel besser, sich Videos dazu anzusehen und habe gar nicht ins Wiki geschaut...

Antworten

Zurück zu „AuD: Programmieraufgaben“