Graph: countEdges

[LukasPhysiker]

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]

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

[tna_wirth]

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.

[tna_wirth]

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.

[LukasPhysiker]

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]

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]

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]

Wird in der Aufgabenstellung im Laufe des Tages nachgetragen. Ist tatsaechlich ein bisschen versteckt. Es steht in einem JavaDoc drin.