Graph: countEdges

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

Graph: countEdges

Beitrag von LukasPhysiker » 18. Jun 2017 20:22

Ich komme gerade bei Graph: countEdges nicht weiter. Hier ist mein Code:

Code: Alles auswählen

private void countEdgesRec(Node<N, E> node, HashSet<Edge<N, E>> edgeSet, HashSet<Node<N, E>> nodeSet)
{
    if(node == null) return;
    if(nodeSet.contains(node)) return;
    nodeSet.add(node);
    for(Edge<N,E> edge : node.getFanOut())
    {
        countEdgesRec(edge.getTargetNode(),edgeSet,nodeSet);
        if(edgeSet.contains(edge)) continue;
        boolean b = false;
        for(Edge<N,E> otherEdge : edge.getTargetNode().getFanOut())
        {
            if(otherEdge.getTargetNode() == node && edgeSet.contains(otherEdge))
            {
                b = true;
                break;
            }
        }
        if(b) continue;
        edgeSet.add(edge);
    }
    
    for(Edge<N,E> edge : node.getFanIn())
    {
        countEdgesRec(edge.getSourceNode(),edgeSet,nodeSet);
        if(edgeSet.contains(edge)) continue;
        boolean b = false;
        for(Edge<N,E> otherEdge : edge.getSourceNode().getFanIn())
        {
            if(otherEdge.getSourceNode() == node && edgeSet.contains(otherEdge))
            {
                b = true;
                break;
            }
        }
        if(b) continue;
        edgeSet.add(edge);
    }
}

Code: Alles auswählen

public int countEdgesInConnectedGraph(Node<N, E> node)
{
    if(node == null) return -1;
    if(!contains(node)) return -1;
    
    HashSet<Edge<N, E>> edgeSet = new HashSet<Edge<N, E>>();
    HashSet<Node<N, E>> nodeSet = new HashSet<Node<N, E>>();
    
    countEdgesRec(node,edgeSet,nodeSet);
    
    
    return edgeSet.size();
}
Wie man sieht, habe ich extra dafür gesorgt, dass Kanten, die die gleichen Knoten aber unterschiedliche Richtungen haben, nicht doppelt gezählt werden und keine Kanten ausgelassen werden, indem sowohl fanIn als auch fanOut überprüft wird. Trotzdem behaupten zwei Tests, dass ich zu wenig gezählt habe:

Code: Alles auswählen

Antwort des Servers
Junitreport

    Time – 281

    Testcount – 12

    Failurecount – 2

    Ignorerecount – 0

Failurereport

    Testheadder – testTwoFullyConnectedDirectedGraphs(graph.general.CountEdgesTest)

    Message – The partial graph has an edge amount of 12 but function returned 6 expected:<12> but was:<6>

    Trace

Failurereport

    Testheadder – testTwoFullyConnectedDirectedGraphsWithBridge(graph.general.CountEdgesTest)

    Message – The partial graph has an edge amount of 25 but function returned 13 expected:<25> but was:<13>

    Trace 
Hier scheint wenigstens eindeutig zu sein, was mein Algorithmus falsch macht, aber mal wieder bin ich mir nicht sicher, ob es nicht einfach ein Fehler im Test ist.

Kann mir jemand helfen?

Julian Prommer
Moderator
Moderator
Beiträge: 167
Registriert: 17. Apr 2013 15:48

Re: Graph: countEdges

Beitrag von Julian Prommer » 19. Jun 2017 10:38

Ich lasse überprüfen, ob da was mit den Tests falsch lief.
AuD Orga

tna_wirth
Neuling
Neuling
Beiträge: 9
Registriert: 20. Okt 2013 23:51

Re: Graph: countEdges

Beitrag von tna_wirth » 19. Jun 2017 12:49

Du hast Recht. Da ist ein Fehler drin. Von der Idee der Implementierung her, ist dieser aber nicht in den Tests, sondern in einer falschen Spezifikation in der Aufgabenstellung. Dort heisst es an einer Stelle:
Note, that there are directed and undirected graphs. If there are two edge objects A, B with A.linkedTo(B), these are only counted as one edge. (HINT: check for one edge and divide through two if needed)
Es sollte aber korrekterweise heissen:
Note, that there are directed and undirected graphs. If there are two edge objects A, B with A.linkedTo(B), these are only counted as one edge, iff the graph is undirected. (HINT: check for one edge and divide through two if needed)
Mit dieser Korrektur passen die Tests zur Aufgabenstellung. Ausserdem fuehrt das meines Erachtens nach zu einer deutlich schlankeren Loesung. Aktualisierte Version wird dann folgen, sobald Nabla wieder laeuft.

Ich hoffe, ich konnte weiterhelfen.
AuD - Codemonkey - Graphen u. Baeume - Development

tna_wirth
Neuling
Neuling
Beiträge: 9
Registriert: 20. Okt 2013 23:51

Re: Graph: countEdges

Beitrag von tna_wirth » 19. Jun 2017 16:10

Kurzer Nachtrag:
Der Zusatz im JavaDoc waere tatsaechlich streng genommen auch nicht notwendig. In Klammern steht bereits der Hinweis, das es klug ist alle Kanten zu zaehlen, und im Fall eines DirectedGraph die resultierende Anzahl durch zwei zu teilen.

Der Fehler in deinem Ansatz besteht darin, dass du, unabhaengig davon ob der Graph gerichtet oder ungerichtet ist oder nicht, Kanten die zwischen denselben Knoten sind nicht doppelt zaehlst. Das fuehrt zu einem Fehler in den Tests, wenn es sich um einen gerichteten Graphen handelt. Denn dort zwei Kanten die unterschiedliche Richtungen aufweisen, absichtlich als doppelt zu zaehlen.

Ich werde aber der Vollstaendigkeit halber Edge::linkedTo(Edge) auf die Whitelist schreiben, da es im JavaDoc vorkommt.
AuD - Codemonkey - Graphen u. Baeume - Development

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

Re: Graph: countEdges

Beitrag von LukasPhysiker » 19. Jun 2017 16:31

Danke, das werde ich gleich mal ausprobieren, sobald Codemonkeys wieder funktioniert.

Aber wie finde ich im Code heraus, ob ein Graph gerichtet oder ungerichtet ist? Ich meine, da war keine Methode in der Whitelist, die das einem zurückliefern würde.

al.ex
Neuling
Neuling
Beiträge: 3
Registriert: 9. Jun 2017 16:07

Re: Graph: countEdges

Beitrag von al.ex » 19. Jun 2017 19:07

LukasPhysiker hat geschrieben:
19. Jun 2017 16:31
Aber wie finde ich im Code heraus, ob ein Graph gerichtet oder ungerichtet ist? Ich meine, da war keine Methode in der Whitelist, die das einem zurückliefern würde.
Das kannst du mit this instanceof UndirectedGraph prüfen.

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

Re: Graph: countEdges

Beitrag von LukasPhysiker » 19. Jun 2017 22:07

Danke, das hat geklappt! Steht das irgendwo in den Aufgabenstellungen oder hätte ich das riechen sollen? Zumindest in dieser Aufgabe findet man weder DirectedGraph noch UndirectedGraph mit Strg+F.

tna_wirth
Neuling
Neuling
Beiträge: 9
Registriert: 20. Okt 2013 23:51

Re: Graph: countEdges

Beitrag von tna_wirth » 20. Jun 2017 12:20

Wird in der Aufgabenstellung im Laufe des Tages nachgetragen. Ist tatsaechlich ein bisschen versteckt. Es steht in einem JavaDoc drin.
AuD - Codemonkey - Graphen u. Baeume - Development

Antworten

Zurück zu „AuD: Programmieraufgaben“