Kruskal - doFunctionality: hat jemand eine Lösung?

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

Kruskal - doFunctionality: hat jemand eine Lösung?

Beitrag von LukasPhysiker » 21. Jun 2017 20:14

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
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: Kruskal - doFunctionality: hat jemand eine Lösung?

Beitrag von Kabooom » 21. Jun 2017 20:30

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

Re: Kruskal - doFunctionality: hat jemand eine Lösung?

Beitrag von LukasPhysiker » 21. Jun 2017 21:09

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
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 9. Mai 2017 12:44

Re: Kruskal - doFunctionality: hat jemand eine Lösung?

Beitrag von Vykyfikation » 22. Jun 2017 10:15

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

Re: Kruskal - doFunctionality: hat jemand eine Lösung?

Beitrag von LukasPhysiker » 22. Jun 2017 18:59

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. :D
Das werde ich bestimmt auch noch hinkriegen.

Antworten

Zurück zu „AuD: Programmieraufgaben“