Seite 1 von 1

Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 11. Jun 2017 14:42
von Voleuro
Hallo,

Bin gerade bei der Aufgabe Dijkstra Complete. Habe Die Invariante, Funktionalität etc. aus den kleineren Dijkstra Aufgaben übernommen und die sind auch alle durchgelaufen. Jetzt bekomme ich 13x den Fehler "

Code: Alles auswählen

ava.lang.ClassCastException: 
graph.Node cannot be cast to java.lang.Comparable 
at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:652) 
at java.util.PriorityQueue.siftUp(PriorityQueue.java:647) 
at java.util.PriorityQueue.offer(PriorityQueue.java:344) 
at wrap.substitute.PriorityQueue.offer(PriorityQueue.java:80) 
at java.util.PriorityQueue.add(PriorityQueue.java:321) 
at wrap.substitute.PriorityQueue.add(PriorityQueue.java:56) 
at graph.algorithm.dijkstra.Dijkstra.doFunctionality(Dijkstra.java:254)
Der Stack führ den Fehler auf die doFuncionality Methode zurück, was ich mir aber eigentlich nciht vorstellen kann, da diese ja in der vorigen Aufgabe funktioniert hat. ^^"

Ich würde vermuten, dass der Fehler irgendwo im Preprocessing liegt, da das das einzige ist, was ich für die Aufgabe neu geschrieben habe..

Würde mich freuen, wenn jemand anderes mal über den Code drüber schauen könnte und vielleicht den Fehler findet :)

Hier ist mein Code fürs Preprocessing und der für die Funktionalität:

Code: Alles auswählen

public void preProcess() throws InvalidInputException{
    
    if(getSourceNode() == null || getGraph() == null) {
        throw new InvalidInputException("adad");
    }
    
    ArrayList<Edge<N, E>> edges = getGraph().getEdgeList();
    for(int i=0;i<edges.size();i++) {
        if(getComparator().isNegative(edges.get(i).getData())) {
            throw new InvalidInputException("Blub");
        }
    }
    
    setIterations(0);
    setPredecessors(new HashMap<Node<N, E>, Node<N, E>>());
    setSettled(new HashSet<Node<N, E>>());
    setPaths(new HashMap<Node<N, E>, LinkedList<Node<N, E>>>());
    setDistances(new HashMap<Node<N,E>,E>());
    
    ArrayList<Node<N, E>> nodes = getGraph().getNodeList();
    
    for(int i=0;i<nodes.size();i++) {
        if(nodes.get(i) == getSourceNode()) {
            getDistances().put(nodes.get(i),getComparator().getZero());
        }
        else {
            getDistances().put(nodes.get(i),getComparator().getMax());
        }
    }
    
    PriorityQueue<Node<N, E>> prio = new PriorityQueue<Node<N, E>> ();
    prio.add(getSourceNode());
    setPriorityQueue(prio);
}

Code: Alles auswählen

public void doFunctionality(){
    Node<N,E>               smallest = getSmallestNode();
    HashSet<Node<N, E>>     settled = getSettled();
    ArrayList<Edge<N, E>>   edges =  smallest.getFanOut();
    HashMap<Node<N, E>, E>  distances = getDistances();
    PriorityQueue<Node<N, E>> queue = (PriorityQueue<Node<N, E>>)getPriorityQueue();
    E myDist = distances.get(smallest);
    AbstractEdgeComparator<E> edgeComp = getComparator();
    HashMap<Node<N,E>,Node<N,E>> pre = getPredecessors();
    
    
    
    for(int i=0;i<edges.size();i++) {
        Node<N,E> target = edges.get(i).getTargetNode();

            if(!settled.contains(target)) {
                E dist = distances.get(target);
                
                int cmp = edgeComp.compare(dist,edgeComp.sum(myDist,edges.get(i).getData()));
                
                if(cmp > 0) {
                    distances.put(target,edgeComp.sum(myDist,edges.get(i).getData()));
                    pre.put(target,smallest);
                }
                
                if(!queue.contains(target)) {
                    queue.add((Node<N, E>) target);
                     
                }
            }
    }
    
    queue.remove(smallest);
    settled.add(smallest);
    
    
}
Liebe Grüße und Danke im vorraus :D ,
Kai

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 12. Jun 2017 15:10
von LukasPhysiker
Hallo Kai,

ich habe das selbe Problem. Falls es hilft, poste ich mal meinen eigenen Code:

Code: Alles auswählen

public void preProcess() throws InvalidInputException
{
    G graph = getGraph();
    if (graph == null)
        throw new InvalidInputException();
    if (getSourceNode() == null)
        throw new InvalidInputException();
    ArrayList<Edge<N, E>> edgeList = graph.getEdgeList();
    AbstractEdgeComparator<E> comp = getComparator();
    for (Edge<N, E> edge : edgeList) {
        if (comp.isNegative(edge.getData())) {
            throw new InvalidInputException();
        }
    }
    ArrayList<Node<N, E>> nodeList = graph.getNodeList();
    iterations = 0;
    distances = new HashMap(nodeList.size());
    for (Node<N, E> node : nodeList) {
        distances.put(node, comp.getMax());
    }
    
    predecessors = new HashMap();
    settled = new HashSet();
    paths = new HashMap();
    
    priorityQueue = new PriorityQueue<Node<N, E>>();
    priorityQueue.add(getSourceNode());
}

Code: Alles auswählen

public void executeVariant()
{
    smallestNode = getPriorityQueue().remove();
    setIterations(getIterations()+1);
    settled.add(smallestNode);
}

Code: Alles auswählen

public boolean checkBreakCondition()
{
    return !getPriorityQueue().isEmpty();
}

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. Muss vor dem letzten und nach dem ersten stehen, sonst macht ein Bug in den Tests alles kaputt!
    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();
        }
    }
}

Code: Alles auswählen

public void doFunctionality()
{
    Node<N,E> smallestNode = getSmallestNode();
    HashMap<Node<N, E>, E> distances = getDistances();
    AbstractEdgeComparator<E> comp = getComparator();
    PriorityQueue<Node<N, E>> priorityQueue = getPriorityQueue();
    HashSet<Node<N, E>> settled = getSettled();
	HashMap<Node<N,E>,Node<N,E>> predecessors = getPredecessors();
    
    
    if(iterations == 1)
    {
        distances.put(smallestNode,comp.getZero());
    }
    
    ArrayList<Edge<N, E>> edges = smallestNode.getFanOut();
    
    for(Edge<N,E> edge : edges)
    {
        Node<N,E> node = edge.getTargetNode();
        
        if(!settled.contains(node))
        {
            if(comp.compare(distances.get(node),comp.sum(distances.get(smallestNode),edge.getData())) > 0)
            {
                distances.put(node,comp.sum(distances.get(smallestNode),edge.getData()));
			    predecessors.put(node,smallestNode);
            }
    		
		    if(!priorityQueue.contains(node))
		    {
    			priorityQueue.add(node);
		    }
        }
        
        
        
    }
    
    settled.add(smallestNode);
}
So wie es aussieht, passiert das ja durch den Aufruf von PriorityQueue.add(). Node<N,E> sollte demnach Comparable implementieren, aber darauf haben wir ja keinen Einfluss. Jedenfalls macht es ja Sinn dass eine PriorityQueue Comparables haben will, damit sie die Elemente sortieren kann. Es kann gut sein, dass das mal wieder ein Fehler in der Aufgabe ist, aber ich kann mir auch gut vorstellen, dass ich mir hier einfach blöd anstelle. Ich würde mich auch freuen, wenn jemand eine Lösung dazu finden würde.

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 15. Jun 2017 22:23
von LukasPhysiker
Ich glaube, ich bin der Ursache ein wenig näher gekommen. Die Klasse PriorityQueue hart auch einen Konstruktor public PriorityQueue(int initialCapacity, Comparator<? super E> comparator). Ich habe schon die getComparator()-Funktionen ausprobiert, die in der Liste der erlaubten Funktionen stehen, aber davon hat nichts geholfen. Es sind einfach keine Comparators für Node<N,E>. Diesen Comparator gibt es wahrscheinlich irgendwo, aber das ist nicht in der Aufgabe dokumentiert.

Es wäre schön, mal einen Kommentar von offizieller Seite zu bekommen.

Übrigens hatte mein Code in meinem vorherigen Post Fehler, die ich jetzt korrigiert habe.

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 16. Jun 2017 00:05
von kommiker
Hallo Voleuro,

ich habe das Preprocessing genau so wie du implementiert wie du, ohne deinen Code vorher gesehen zu haben. Ich würde also mal meinen das wir genau das umgesetzt haben, was die Aufgabe beschreibt.
Meine einzelnen Teile, also excuteVariant, checkBreakCondition, checkInvariante und functionality funktionieren ebenfalls alle in den einzelnen Methoden.
Ich bekomme ebenfalls genau die Fehlermeldungen auch!! Ich weis ehrlich gesagt auch nicht woran das liegen könnte...

Deshalb nochmal ganz ausdrücklich an das betreuende Team: Machen wir irgendwo einen Fehler im Code oder ist das ein Nabla Fehler?

Würde wirklich schön sein wenn wir eine Antwort bekommen. Mein Testat rückt immer näher und mit Dijkstra Complete sind nicht gerade wenige Punkte im Testatsfall ausgefüllt... (5/6!)

lg kommiker

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 16. Jun 2017 15:54
von OAEP
Bin auch grad an der Aufgabe.

Die PriorityQueue muss natürlich wissen, wie sie Node vergleichen muss. Node ist scheinbar kein Comparable, also gibts dafür eigentlich den Konstruktor PriorityQueue(int initialCapacity, Comparator<? super E> comparator).
Da der AbstractEdgeComparator in der Aufgabe nur Edge vergleichen kann, denk ich mir folgendes:

PriorityQueue<Node<N,E>> queue = new PriorityQueue<>(10, (n1, n2) -> comp.compare(n1.getData(), n2.getData()));

Codemonkeys meint: "Forbidden function call: compare" Muss man dazu noch was sagen? Ne, ich glaube nicht.

Eine klare Ansage ans Team: Macht unsere Studienleistung nicht von Codemonkeys abhängig, solange das nicht ordentlich funktioniert! Alleine in den Dijkstra Aufgaben gibt es diesen Bug und den bei der Invariante. 2 Bugs, eine Aufgabe. Bei den anderen sieht es kaum besser aus. Ich wollte eigentlich auf den Bonus gehen, aber die Lust ist mir jetzt vergangen. :evil: Und noch was: Die Tests versuchen viel zu oft das Halting Problem und das Codeäquivalenzproblem zu "lösen". Das klappt nicht, siehe FGdI 1. Beispiel: Sort(O(n^2)). Da habe ich den standardmäßigsten Bubblesort und Selectionsort, den es so geben kann, ausprobiert. Bei beidem Timeout mit 500ms. Und wie viele Elemente will der Test da sortieren? 1 Milliarde? In 500ms mit O(n^2)? Keine Ahnung, der Test sagt es mir nicht.

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 16. Jun 2017 16:40
von gerigeri
PriorityQueue soll so implementiert werden:

Code: Alles auswählen

setPriorityQueue(new PriorityQueue<Node<N,E>>(11, getQueueComparator()));

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 16. Jun 2017 17:17
von kommiker
Vielen vielen Dank!:D

Tatsache! 21/22 Tests bestanden! Den einen Fehler finde ich schon noch.

Wo war die Methode gelistet? Ist sie gelistet? Ich habe sie nicht gefunden. Das ist das perfekte Beispiel wie mehrere Studenten ein komplexes Problem verstanden haben und trotzdem von Codemonkey bestraft werden!

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 16. Jun 2017 17:24
von gerigeri
Kannst du es beim A* sehen, aber auch selbst implementieren mit einer anonymen classe:

Code: Alles auswählen

setPriorityQueue(new PriorityQueue<Node<N,E>>(11,new Comparator<Node<N,E>>(){
	@Override
	public int compare(Node<N,E> n1, Node<N,E> n2){
		return getComparator().compare(getDistances().get(n1),getDistances().get(n2));
	}
}));

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 19. Jun 2017 13:07
von tna_wirth
Wunderschoenen guten Tag,

ich moechte die verspaetete Antwort entschuldigen. Die letzte hier gepostete Loesung ist an der Musterloesung schon nahe dran, jedoch viel zu weit gegriffen. Meinem Kenntnisstand nach existiert in der Whitelist eine Methode namens getQueueComparator(). Diese liefert den Comparator fuer die PriorityQueue bereits.

Sollte diese wider erwarten nicht in der Whitelist auftauchen, bitte ich darum, noch einmal Bescheid zu sagen. Ich kann es leider zur Zeit nicht pruefen, da CodeMonkey down ist.

Ich hoffe ich konnte, kenn auch verspaetet, weiterhelfen.

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 19. Jun 2017 16:34
von LukasPhysiker
Ich kann jetzt schonmal Bescheid sagen, dass diese Methode in der Whitelist gefehlt hat, als ich das letzte Mal versucht habe, diese Aufgabe zu machen. Sonst hätten wir die ganzen Probleme in diesem Thread wahrscheinlich gar nicht gehabt...

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 20. Jun 2017 22:13
von kommiker
getQueueComparator() ist immer noch nicht gelistet.

lg kommiker

Re: Dijkstra - Complete - graph.Node cannot be cast to java.lang.Comparable

Verfasst: 24. Jun 2017 11:50
von Voleuro
Hi,
Sorry für die Späte Antwort. Vielen Dank Leute, jetzt laufen bei mir auch 21/22 Tests.. :D
Und das mit getQueueComparator() ist ja mal wieder irgendwie typisch. :roll: Aber so lange sich darum gekümmert wird ist ja alles in ordnung..

LG,
Kai