Kruskal - doFunctionality: hat jemand eine Lösung?

[LukasPhysiker]

Ich stehe gerade voll auf dem Schlauch. Ich verstehe nicht, wie man connected, union, usw. anwenden soll...

Hier ist das erbärmliche Ergebnis meiner bisherigen Versuche:

Code: Alles auswählen

public void doFunctionality()
{
    //try{
    Edge<N,E> smallestEdge = getSmallestEdge();
    
    //UnionFind unionFind = new UnionFind(getMst());
    
    if(!connected(smallestEdge.getSourceNode(),smallestEdge.getTargetNode()))
    {
        //getMst().addEdge(smallestEdge.getSourceNode(),smallestEdge.getTargetNode(),smallestEdge.getData());
        union(smallestEdge.getSourceNode(),smallestEdge.getTargetNode());
    }
    
    
    //}catch(FanOverflowException e){}
}

Ich wäre sehr dankbar, wenn jemand eine funktionierente Lösung posten würde.

PS: Das selbe gilt für Kruskal: UnionFind.

[Kabooom]

Hallo Lukas,

in doFunctionality sollst du mithilfe der Methode connected überprüfen, ob der Source- und Target-Knoten von smallestEdge bereits im Graphen verbunden sind. Nur wenn das nicht der Fall ist, soll man mit try/catch versuchen, dem mst diese Kante hinzuzufügen und die beiden Knoten zu vereinigen mit union(source, target). Das catch soll dabei eine mögliche FanOverflowException abfangen.

In der Methode union werden die spannbäume von zwei Knoten vereinigt. Dabei ist ein Spannbaum so repräsentiert, dass ein Knoten in diesem Spannbaum der parent (HashMap parents) von allen anderen Knoten in diesem Spannbaum ist bzw. parent vom parent etc. . Um die Spannbäume zu vereinigen, müssen dann nur die parent-Knoten der beiden zu verarbeiteten Knoten verbunden werden, indem einer der parent vom anderen wird (Die Details dazu stehen recht verständlich in der Aufgabenstellung).

[LukasPhysiker]

Hallo Kabooom,

danke für deine Antwort! Ich konzentriere mich erstmal darauf, doFunctionality() hinzukriegen, UnionFind gibt ja 0 Punkte...

So wie du das beschreibst, sollte das ja eigentlich schon funktionieren:

Code: Alles auswählen

public void doFunctionality()
{
    if(!connected(smallestEdge.getSourceNode(),smallestEdge.getTargetNode()))
    {
        try
        {
            getMst().addEdge(smallestEdge.getSourceNode(),smallestEdge.getTargetNode(),smallestEdge.getData());
        }
        catch(FanOverflowException e)
        {
            
        }
        union(smallestEdge.getSourceNode(),smallestEdge.getTargetNode());
    }
}

Jetzt bekomme ich aber folgende Fehler:

Code: Alles auswählen

Antwort des Servers
Junitreport

    Time – 34

    Testcount – 3

    Failurecount – 3

    Ignorerecount – 0

Failurereport

    Testheadder – staticSimpleTest(graph.algorithm.kruskal.KruskalFunctionalityTest)

    Message – The MST should be cycle free

    Trace

Failurereport

    Testheadder – staticTestUndirectedGraph(graph.algorithm.kruskal.KruskalFunctionalityTest)

    Message – The MST should be cycle free

    Trace

Failurereport

    Testheadder – testDynamicMST(graph.algorithm.kruskal.KruskalFunctionalityTest)

    Message – The MST should be cycle free

    Trace 

Der MST ist also nicht zykelfrei. Ich dachte, das wird von connected abgefangen? Oder übersehe ich hier noch etwas?

[Vykyfikation]

die Funktion addEdge erwartet als Übergabeparameter zwei Integer und einmal E. Du übergibst jedoch zwei mal Node und einmal E. Mit der Methode getId() bekommst du einen passenden Integer und es funktioniert

Fertig schaut der code dann so aus:

Code: Alles auswählen

{
    
    //Wenn der mst mit der kleinsten Kante smallestEdge keinen Kreis bildet, füge diese Kante dem mst hinzu und update die union find. 
    Edge<N, E> small= getSmallestEdge();
    if(!connected(small.getSourceNode(),small.getTargetNode())){
        try{
            getMst().addEdge(small.getSourceNode().getId(),small.getTargetNode().getId(),small.getData());
        }catch(FanOverflowException e){
            
        }
        union(smallestEdge.getSourceNode(),smallestEdge.getTargetNode());
    }
}

Danke für den Anfang jetzt muss ich noch verstehen, warum man den start mit dem Zielknoten verbinden soll und wie genau Kruskal funktioniert

[LukasPhysiker]

Aaah, danke! Ich hätte vielleicht mal genauer auf das Javadoc von addEdge sehen sollen, da steht ja drin, dass es ints und keine Nodes erwartet.

Wenn man die complete-Aufgaben und unionFind, das ja anscheinend 0 Punkte gibt und SelectionSort, das ja verbuggt ist, nicht mitzählt, habe ich jetzt alles hingekriegt außer Astern: functionality.
Das werde ich bestimmt auch noch hinkriegen.