TDD-Beispiel 2: kürzeste Pfade in Graphen

[mrBrown]

Jetzt mal ein etwas größeres Beispiel als FizzBuzz zu Test Driven Development: Finden eines kürzesten Pfads in ungerichteten Graphen.
Das Beispiel findet man öfters mal im Netz, auch mit unterschiedlichen "Lösungswegen", und ich kann jedem nur empfehlen, das mal selbst zu versuchen. (Wobei das eigentlich für jedes Beispiel gilt, das Bowling-Kata und Sortieren eines Arrays sind auch schöne Beispiele.)

Das ganze ist weniger Tutorial und mehr einfach nur ein Beispiel um es mal zu zeigen, bei Fragen aber einfach was sagen
Der ganze Code findet sich im Repo, potentiell geh ich hier auch nicht auf jede Kleinigkeit ein, aber für einen Überblick sollte es trotzdem auch hier reichen.


Erster Testfall

Der erste Testfall ist wieder, wie üblich, einer der "nichts" macht. In diesem Fall ist es das Suchen eines Pfades in einem leeren Graph.
Um den Testfall zu schreiben, muss man sich aber zumindest ein grundsätzliches Format für die Eingabe des Graphen und des Start- und Zielpunkts überlegen. In diesem Fall wieder das einfachst möglichstes: einfach Strings, jeder "Punkt" im Graphen ist einfach ein Buchstabe, und der Graoh selber ist erstmal ein leerer String.
Das ganze als JUnit-Test:

@Test
void shouldFindNoPathInEmptyGraph() {
    String emptyGraph = "";
    String path = findPath("A", "Z", emptyGraph);

    Assertions.assertThat(path).isEmpty();
}

Und direkt auch der Code, der den Test erfüllt:

private String findPath(final String from, final String to, final String graph) {
    return "";
}

Zusätzlich zu dem ersten Testfall gibt es noch ein paar weiter, die damit auch direkt abgehandelt sind, z.B. der Weg von A nach Z, wenn nur eine Kante von B nach X existiert.
Mit den ersten Kante legt man dann auch das Format für Kanten fest, in diesem Fall einfach Startknoten, Zielknoten und Länge hintereinander, also z.B. BX1.
Das ganze wieder mit JUnit:

@ParameterizedTest
@CsvSource({
        "A,Z,''", // leerer Graph
        "A,Z,BZ1", // einziger Weg hat nicht den gewünschten Pfad
        "A,Z,AX1", // einziger Weg hat nicht das gewünschte Ziel
        "A,Z,BX1", // einziger Weg hat weder gewünschtes Ziel noch Start
})
void shouldReturnEmptyPathIfNoneExist(final String from, final String to, final String graph) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEmpty();
}

Das nächst einfache ist dann ein Graph mit einer Kante, in der genau diese Kante gesucht wird:

@Test
void shouldReturnPathIfOnlyThisPathExists() {
    String graph = "AZ1";
    String path = findPath("A", "Z", graph);

    Assertions.assertThat(path).isEqualTo("AZ");
}

Und der Code, der das erfüllt, ist dann auch wieder nahezu trivial: Wenn der Graph mit der gesuchten Kante anfängt, ist das der gesuchte Pfad

private String findPath(final String from, final String to, final String graph) {
    if (graph.startsWith(from + to)) {
        return from + to;
    }
    return "";
}

Allerdings sollte der Graph ungerichtet sein, also sollte der gleiche Pfad auch gefunden werden, wenn der Graph nur die Kante "ZA1" enthält.
Also den Testfall noch ergänzen:

@ParameterizedTest
@CsvSource({
        "A,Z,AZ1, AZ", // Pfad ist einziger Weg
        "A,Z,ZA1, AZ", // Pfad ist umgekehrt vorhanden
})
void shouldReturnPathIfOnlyThisPathExists(final String from, final String to, final String graph, final String expectedPath) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEqualTo(expectedPath);
}

Und die Implementation entsprechend anpassen:

private String findPath(final String from, final String to, final String graph) {
    if (graph.startsWith(from + to)) {
        return from + to;
    }
    if (graph.startsWith(to + from)) {
        return from + to;
    }
    return "";
}

Erstes Refactoring

Der Code in findPath ist allerdings nicht grad sonderlich schön, besonders das graph.startsWith(from + to) schafft es gar nicht, irgendeine Intention dahinter auszudrücken.
Also schon mal ein kleines Refactoring:

Der Graph besteht ja auch Kanten (beziehungsweise bisher aus genau einer Kante), also könnte man genau diese jetzt als Klasse einführen, und es dem String ein Kanten-Objekt basteln:

record Edge(String from, String to, int length) {}

private Edge parseEdge(final String graph) {
    String from = graph.substring(0, 1);
    String to = graph.substring(1, 2);
    String length = graph.substring(2, 3);

    return new Edge(from, to, Integer.parseInt(length));
}

Und das ganze dann in findPath nutzen:

private String findPath(final String from, final String to, final String graph) {
    Edge edge = parseEdge(graph);
    if (edge.from().equals(from) && edge.to().equals(to)) {
        return from + to;
    }
    if (edge.from().equals(to) && edge.to().equals(from)) {
        return from + to;
    }
    return "";
}

Das Zusammenbauen des Rückgabewerts ist zwar immer noch nicht sonderlich schön, aber zumindest ausreichen – und die Bedingungen sind jetzt schon mal deutlich schöner.

Weiter gehts morgen...

 

[mrBrown]

Und weiter mit dem nächsten Testfall: Bisher besteht der Graph immer aus einer einzelnen Kante, die nächste Stufe wären also zwei Kanten, wobei eine der gesuchte Pfad ist.
(Um's etwas kürzer zu machen, werden's direkt zwei Testfälle, der erste davon würde auch ohne Änderung derfolgreich durchlaufen)

@ParameterizedTest
@CsvSource({
        "A,Z,'AZ1\nBX1', AZ", // Pfad ist als erster vorhanden
        "A,Z,'BX1\nZA1', AZ", // Pfad ist als letzter vorhanden
})
void shouldReturnCorrectPathIfGraphContainsMultipleEdged(final String from, final String to, final String graph, final String expectedPath) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEqualTo(expectedPath);
}

Die Tests schlagen wie erwartet fehl, da nur die erste Kante des Graphen berücksichtig wird.
Um alle Kanten zu berücksichtigen muss also einen Schleife drum, einmal um das parsen des Graphen und um das Suchen der Kante:

private String findPath(final String from, final String to, final String graph) {
    List<Edge> edges = parseEdges(graph);

    for (final Edge edge : edges) {
        if (edge.from().equals(from) && edge.to().equals(to)) {
            return from + to;
        }
        if (edge.from().equals(to) && edge.to().equals(from)) {
            return from + to;
        }
    }
    return "";
}

private List<Edge> parseEdges(final String graph) {
    var lines = graph.split("\n");

    List<Edge> edges = new ArrayList<>();
    for (var line : lines) {
        if (!line.isEmpty()) {
            edges.add(parseEdge(line));
        }
    }
    return edges;
}

Dann wieder ein bisschen Refactoring:
Das Parsen der Edges kann in eine eigene Klasse gezogen werden, die Pfadsuche und die Edges selber genauso. Die Prüfung, ob eine Kante zwei Punkte verbindet, kann man auch in die Edge-Klasse auslagern.

findPath in der Testklassen verkürzt sich dann zu:

private String findPath(final String from, final String to, final String graph) {
    List<Edge> edges = new EdgeParser().parseEdges(graph);

    List<Edge> path = new PathFinder(edges).findPath(from, to);

    List<String> nodes = new ArrayList<>();
    if (!path.isEmpty()) {
        nodes.add(from);
        nodes.add(path.get(0).to());
    }

    return String.join("", nodes);
}

Dann wieder der nächste Testfall: bisher werden nur Pfade gefunden, die genau aus einer existierenden Kante bestehen – es sollen aber natürlich auch Pfade gefunden werden, die aus mehreren Kanten bestehen.
Also als nächsten Testfall einen Graphen mit zwei Kanten, und der gesuchte Pfad geht durch beide:

@ParameterizedTest
@CsvSource( {
        "A,Z,'AB1\nBZ1', ABZ",
})
void shouldReturnPathIfItConsistOfTwoEdges(final String from, final String to, final String graph, final String expectedPath) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEqualTo(expectedPath);
}

Die erfüllen das Tests ist etwas mehr als bisher (es wäre vielleicht einfacher gewesen, diesen Fall mit dem vorherigen zu tauschen, das ganze wäre dann etwas aufgeteilter.)
Erstmal muss in der Testklasse der Egebnis-String jetzt aus mehreren Kanten zusammengebaut werden (spar ich mir hier mal).
Dann muss die Implementierung selbst angepasst werden. Es muss erst die Kanten gefunden werden, die beim Startknoten losgeht, und dann die Kante, die am Ziel der vorherigen Kante beginnt (und da der Graph ungerichtet ist, darf man dabei nicht nochmal die zuerst besuchte Kante finden). Ist damit irgendein pfad gefunden, muss noch getestet werden, ober auc wirklich bis zum gesuchten Ziel findet, sonst schlagen die ersten Tests fehl.

Einfachste (wenn auch nicht sehr schöne) Lösung dafür:
findEdgeFrom sucht im Graphen eine Kante, die vom übergebenen Punkt weg führt, und stellt dabei sicher, dass man nicht wieder an einem Punkt landet, an dem man schon war.
startOf und endOf geben einfach nur den ersten/letzten Punkt des gesamten Pfades zurück

List<Edge> findPath(final String from, final String to) {
    List<Edge> path = new ArrayList<>();
    List<String> visited = new ArrayList<>();

    Edge edge = findEdgeFrom(from, visited);
    if (edge != null) {
        visited.add(edge.from());
        path.add(edge);
        edge = findEdgeFrom(edge.to(), visited);
        if (edge != null) {
            visited.add(edge.from());
            path.add(edge);
        }
    }

    if (!path.isEmpty()) {
        if (startOf(path).equals(from) && endOf(path).equals(to)) {
            return path;
        }
    }

    return List.of();
}

Tests laufen damit schon mal wieder durch, also den nächsten Testfall. Bisher darf der Pfad maximal aus zwei Kanten bestehen, mehr sollen natürlich auch möglich sein, z.B drei:

@ParameterizedTest
@CsvSource( {
        "A,Z,'AB1\nBZ1', ABZ",
        "A,Z,'AB1\nBC1\nCZ1', ABCZ",
})
void shouldReturnPathIfItConsistOfMultipleEdges(final String from, final String to, final String graph, final String expectedPath) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEqualTo(expectedPath);
}

Und zum Erfüllen wird einfach das verschachtelte if zu einer while-Schleife umgebaut:

List<Edge> findPath(final String from, final String to) {
    List<Edge> path = new ArrayList<>();
    List<String> visited = new ArrayList<>();

    Edge edge = findEdgeFrom(from, visited);
    while (edge != null) {
        visited.add(edge.from());
        path.add(edge);
        edge = findEdgeFrom(edge.to(), visited);
    }

    if (!path.isEmpty()) {
        if (startOf(path).equals(from) && endOf(path).equals(to)) {
            return path;
        }
    }

    return List.of();
}

 

[mrBrown]

Bisher müssen alle Kanten im Graph eine lange Linie bilde, Abzweigungen sind noch nicht möglich. Also kommen die als nächstes:

@ParameterizedTest
@CsvSource({
        "A,Z,'AB1\nBC1\nCX1\nCZ1', ABCZ",
})
void shouldReturnPathIfBranchesExist(final String from, final String to, final String graph, final String expectedPath) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEqualTo(expectedPath);
}

Die Implementierung merkt sich aktuell nur, bei welchem Knoten sie aktuell ist und wie der Pfad dorthin aussieht, und geht von dort weiter.
Mit Abzweigungen klappt das so nicht mehr – jeder Knoten hat ja mehrere Nachfolger, man muss sich also irgendwie alle Pfade merken und bei mehreren Knoten den Weg fortsetzen.

Also zwei Dinge ändern: Die einzelne gemerkte Kante (die zum merken des "aktuellen" Knotens da war) ersetzen wir einfach durch eine Liste von Knoten, damit wir uns mehrere merken können.
Den einzelnen Pfad erstetzen wir durch eine Map, die dann jeweils den Pfad bis zu einem Knoten enthält.
Sowohl Liste als auch die Map initialisieren wir dann mit dem Startknoten – an diesem müssen wir Starten und der Pfad dorthin ist ein leerer Pfad.
findEdgeFrom wurde nebenbei durch findEdgesFrom ersetzt, wir brauchen ja jetzt alle abgehenden Kanten, nicht nur die eine.

List<Edge> findPath(final String from, final String to) {
    Map<String, List<Edge>> allPaths = new HashMap<>();

    List<String> visited = new ArrayList<>();
    List<String> next = new ArrayList<>();

    allPaths.put(from, List.of());
    next.add(from);

    while (!next.isEmpty()) {
        String nextFrom = next.remove(0);
        List<Edge> edges = findEdgesFrom(nextFrom, visited);

        for (final Edge edge : edges) {
            List<Edge> pathTo = new ArrayList<>(allPaths.get(nextFrom));
            pathTo.add(edge);
            allPaths.put(edge.to(), pathTo);
            next.add(edge.to());
        }

        visited.add(nextFrom);
    }

    if (allPaths.containsKey(to)) {
        return allPaths.get(to);
    }

    return List.of();
}

Der korrekte Pfad wird jetzt auch gefunden, wenn es Abzweigungen gibt.


Eines wurde bisher aber noch nicht berücksichtig: Es soll ja nicht nur irgendeine Pfad gefunden werden, sondern der kürzeste. Also erstmal einen Testfall dafür hinzufügen.
Es gibt einen Weg direkt zum Ziel, der ist aber Länger als der Weg über zwei Kanten:

@ParameterizedTest
@CsvSource( {
        "A,Z,'AZ3\nAB1\nBZ1', ABZ",
})
void shouldReturnShortestPath(final String from, final String to, final String graph, final String expectedPath) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEqualTo(expectedPath);
}

Wenn man sich jetzt auf die Suche nach dem Fehler macht, z.B. mit dem Debugger, sieht man das die Reihenfolge, in der die Knoten betrachtet werden, das Problem ist:
Zuerst wird die Kante von A nach Z betrachtet, dann die von A nach B, dann die von Z nach B – der Weg von B nach Z wird also gar nicht betrachtet.

Der Weg nach Z ist länger als der Weg nach B – damit also der Knoten B vorher betrachtet wird, könnte man einfach den Knoren raussuchen, welche den kürzesten Pfad hat, und von diesem aus weiter machen. Also, statt einfach immer den ersten Knoten aus der Liste zu nehmen, suchen wir das Minimum ...

private String removeMin(final List<String> next, final Map<String, List<Edge>> allPaths) {
    record LengthTillNode(String node, int length) { };

    LengthTillNode min = next.stream().map(n -> new LengthTillNode(n, length(allPaths.get(n))))
            .min(Comparator.comparingInt(LengthTillNode::length))
            .orElseThrow();

    next.remove(min.node);
    return min.node;
}

... und ersetzen dann einfach String nextFrom = next.remove(0); durch String nextFrom = removeMin(next, allPaths);. Die Tests laufen damit jetzt auch wieder erfolgreich durch.


Kurz über den Code nachdenken: was passiert, wenn zwei Wege zum Ziel gefunden werden, und der erste von beiden der kürzere ist – also der Gegenteilige Fall des vorherigen Tests.

@ParameterizedTest
@CsvSource( {
        "A,Z,'AZ3\nAB1\nBZ1', ABZ",
        "A,Z,'AC3\nCZ10\nAB2\nBZ2', ABZ",
})
void shouldReturnShortestPath(final String from, final String to, final String graph, final String expectedPath) {
    String path = findPath(from, to, graph);

    Assertions.assertThat(path).isEqualTo(expectedPath);
}

Der Testfall schlägt fehl, da der später gefundene längere Pfad den vorherigen, kürzeren, überschreibt. Also in findPath genau das verhindern, in dem man den Pfad nur überschreibt, wenn er kürzer ist:

   for (final Edge edge : edges) {
        List<Edge> pathTo = new ArrayList<>(allPaths.get(nextFrom));
        pathTo.add(edge);
        if (allPaths.get(edge.to()) == null || length(pathTo) < length(allPaths.get(edge.to()))) {
            allPaths.put(edge.to(), pathTo);
            next.add(edge.to());
        }
    }

Danach ist dann auch der Testfall erfolgreich.

 

[mrBrown]

Und einmal die gesamte Implementierung (noch ohne abschließendes Refactoring).

Wer erkennt den Algorithmus?

import java.util.*;

record Edge(String from, String to, int length) {
    public Edge reverse() {
        return new Edge(this.to(), this.from(), this.length());
    }
}

public class PathFinder {

    private final List<Edge> edges;

    public PathFinder(final List<Edge> edges) {
        this.edges = edges;
    }

    List<Edge> findPath(final String from, final String to) {
        Map<String, List<Edge>> allPaths = new HashMap<>();

        List<String> visited = new ArrayList<>();
        List<String> next = new ArrayList<>();

        allPaths.put(from, List.of());
        next.add(from);

        while (!next.isEmpty()) {
            String nextFrom = removeMin(next, allPaths);
            List<Edge> edges = findEdgesFrom(nextFrom, visited);

            for (final Edge edge : edges) {
                List<Edge> pathTo = new ArrayList<>(allPaths.get(nextFrom));
                pathTo.add(edge);
                if (allPaths.get(edge.to()) == null || length(pathTo) < length(allPaths.get(edge.to()))) {
                    allPaths.put(edge.to(), pathTo);
                    next.add(edge.to());
                }
            }

            visited.add(nextFrom);
        }

        if (allPaths.containsKey(to)) {
            return allPaths.get(to);
        }

        return List.of();
    }

    private String removeMin(final List<String> next, final Map<String, List<Edge>> allPaths) {
        record LengthTillNode(String node, int length) { };

        LengthTillNode min = next.stream().map(n -> new LengthTillNode(n, length(allPaths.get(n))))
                .min(Comparator.comparingInt(LengthTillNode::length))
                .orElseThrow();

        next.remove(min.node);
        return min.node;
    }

    private int length(List<Edge> path) {
        return path.stream().mapToInt(Edge::length).sum();
    }

    private List<Edge> findEdgesFrom(String from, final List<String> visited) {
        List<Edge> edges = new ArrayList<>();
        for (final Edge edge : this.edges) {
            if (edge.from().equals(from) && !visited.contains(edge.to())) {
                edges.add(edge);
            }
            if (edge.to().equals(from)  && !visited.contains(edge.from())) {
                edges.add(edge.reverse());
            }
        }
        return edges;
    }
}

 

[mrBrown]

@temi wenn ich mich Recht erinnere hattest du irgendwann mal nach einem "größerem" Beispiel mit TDD gefragt, was näher an echter Entwicklung ist, deshalb schon mal ein Ping an dich

 

[mrBrown]

Und ums schon mal direkt vorneweg zu nehmen; mit der Wahl (bzw eher der Reihenfolge) der Testfälle bin ich selbst nicht 100% zufrieden, u.U. wäre da am manchen Stellen was anderes besser gewesen. Da darf sich jetzt gerne jeder zu auslassen


Und um noch was anderes vorneweg zu nehmen: wer den Algorithmus kennt wird auch die verbesserte Variante davon kennen. Wenn man nur das Ergebnis selbst betrachtet, kommt man mit TDD nicht dorthin, das Ergebnis ist in jedem Fall ja der optimale Pfad. Wenn man mit TDD dorthin kommen wollen würde, würde man zB einen Listener für den jeweils betrachteten Knoten einführen. Über geschickte Wahl der Testfälle würde man dann auch zu einer Heuristik kommen — der Graph muss das dafür natürlich zulassen, für im obigen Beispiel könnte man zB die Entfernung zweier Buchstaben nutzen, allerdings sind die Gewichte bisher natürlich nicht entsprechend gewählt.

 

[mihe7]

Wenn man nur das Ergebnis selbst betrachtet, kommt man mit TDD nicht dorthin, das Ergebnis ist in jedem Fall ja der optimale Pfad. Wenn man mit TDD dorthin kommen wollen würde, würde man zB einen Listener für den jeweils betrachteten Knoten einführen.

Es geht in meinen Augen nicht darum, mit TDD Algorithmen zu finden (den zu implementierenden Algorithmus kennt man ja in der Regel grob im Voraus), sondern um die veränderte Perspektive. Der Produktivcode muss zwangsweise testbar sein und man (zumindest ich) denkt einfach anders.

Wenn ich die findPath-Methode einfach so implementieren würde, hätte ich einen gewisse Vorstellung von einem Graphen und dem Algorithmus im Kopf (ggf. sogar mit Zeichnung auf Papier) und wäre damit beschäftigt, mir zu überlegen, wie ich den Algorithmus in Code gieße. Am Ende und nach ein paar Korrekturen kommt dann in der Regel etwas halbwegs brauchbares raus.

Bei TDD ändert sich das radikal. Klar, ich will auch hier eine findPath-Methode aber da habe ich die Doppelrolle des Testers inne und versuche somit von vornherein, unterschiedliche Situtationen zu betrachten: was soll passieren, wenn der Graph leer ist? Was soll passieren, wenn Quell- und Zielknoten identisch sind? Was könnte ich als nächstes testen, um meinen Code ein Stück näher ans gewünschte Ergebnis zu bringen? All das sind Dinge, um die man sich sonst meist wenig Gedanken macht und auch, wenn sie dann nicht in den Testcode Einzug halten, weil der Produktivcode davon nicht profitiert, so hat man sich wenigstens mit ihnen auseinandergesetzt.

 

[mrBrown]

Es geht in meinen Augen nicht darum, mit TDD Algorithmen zu finden (den zu implementierenden Algorithmus kennt man ja in der Regel grob im Voraus), sondern um die veränderte Perspektive.

Da bin ich total deiner Meinung

ich wollte nur schon mal direkt auf das „TDD funktioniert ja gar nicht weil der Algorithmus ist ja schlecht“ Argumen reingehen, was man dabei ziemlich oft hört...