Kürzeste Wege in iOS prüfen: Gewichte, Erreichbarkeit und Überlauf

Offline-Navigation, Routen auf einem Campus oder die Planung von Abläufen innerhalb einer App können es erfordern, kürzeste Wege direkt im iOS-Client zu berechnen. Mit gewöhnlichen Testfällen liefert der Algorithmus zwar Entfernungen; bei Nullzyklen, nicht verbundenen Knoten oder sehr großen Gewichten können jedoch plausibel wirkende, falsche Ergebnisse entstehen. Eine kleine, übersichtliche Swift-Referenzimplementierung auf einem Cloud-Mac hilft dabei, algorithmische Regressionen gezielter einzugrenzen, als lediglich Routen in der Oberfläche anzuklicken.

Zuerst den Vertrag für Graph und Ergebnisse festlegen

Dieser Artikel verwendet gerichtete Graphen mit bei null beginnenden Knotennummern und nicht negativen Kantengewichten vom Typ Int64. Für ungerichtete Straßen müssen ausdrücklich Kanten in beiden Richtungen angelegt werden. Die Entfernung vom Startknoten zu sich selbst beträgt null; für unerreichbare Knoten wird nil zurückgegeben. Weder null noch der größte darstellbare Integerwert darf als Kennzeichnung für Unerreichbarkeit dienen.

Bei der Eingabe müssen der Startknoten, sämtliche Zielknoten der Kanten und negative Gewichte geprüft werden – auch in Teilgraphen, die vom Start aus nicht erreichbar sind. Parallele Kanten sind zulässig; der Algorithmus soll die kürzere wählen. Auch Schleifen sind erlaubt, dürfen aber keine endlosen Aktualisierungen auslösen.

Dijkstra setzt nicht negative Gewichte voraus. Negative Werte durch null zu ersetzen, „repariert“ die Eingabe nicht, sondern verändert die fachliche Problemstellung.

Wenn der Graph mit ganzzahligen Einheiten wie Metern oder Millisekunden aufgebaut wird, muss die Genauigkeit bereits bei der Datenumwandlung festgelegt werden. Entfernungen nicht erst mit Gleitkommazahlen berechnen und anschließend kurzerhand auf Ganzzahlen abschneiden: Sonst vergleichen die Tests nicht mehr denselben Graphen.

Ein gut prüfbares Referenzmodell schreiben

Die folgende Implementierung durchsucht die Knoten nacheinander, um den nächsten auszuwählen. Ihre Zeitkomplexität beträgt O(V²＋E), ihr Speicherbedarf O(V). Sie eignet sich zur Abnahme kleiner Graphen, nicht als Nachweis für die Leistungsfähigkeit des Produktionsalgorithmus auf großen Karten. Den Code als shortest-path.swift speichern und die folgenden Testfälle an dieselbe Datei anhängen.

enum GraphError: Error {
    case invalidVertex
    case negativeWeight
    case overflow
}

struct Edge {
    let to: Int
    let weight: Int64
}

func distances(
    _ graph: [[Edge]],
    from source: Int
) throws -> [Int64?] {
    guard graph.indices.contains(source) else {
        throw GraphError.invalidVertex
    }

    for edges in graph {
        for edge in edges {
            guard graph.indices.contains(edge.to) else {
                throw GraphError.invalidVertex
            }
            guard edge.weight >= 0 else {
                throw GraphError.negativeWeight
            }
        }
    }

    var result = Array<Int64?>(repeating: nil, count: graph.count)
    var settled = Array(repeating: false, count: graph.count)
    result[source] = 0

    for _ in graph.indices {
        var selected: Int?
        for vertex in graph.indices where !settled[vertex] {
            guard let value = result[vertex] else { continue }
            if let current = selected {
                if value < result[current]! {
                    selected = vertex
                }
            } else {
                selected = vertex
            }
        }

        guard let vertex = selected else { break }
        settled[vertex] = true
        let base = result[vertex]!

        for edge in graph[vertex] where !settled[edge.to] {
            let (candidate, overflow) =
                base.addingReportingOverflow(edge.weight)
            guard !overflow else { throw GraphError.overflow }

            if let previous = result[edge.to] {
                if candidate < previous {
                    result[edge.to] = candidate
                }
            } else {
                result[edge.to] = candidate
            }
        }
    }

    return result
}

Dieses Modell liefert ausschließlich Entfernungen und speichert keine Vorgänger. So bleibt die Rekonstruktion von Wegen von der Prüfung der Entfernungen getrennt. Knoten mit gleicher Entfernung werden in der Reihenfolge ihrer Nummern verarbeitet, damit sich Ergebnisse reproduzieren lassen. Die Anwendungslogik darf sich jedoch nicht auf diese Reihenfolge verlassen.

Grenzfälle mit festen Testdaten absichern

Zunächst kommt ein kleiner Graph mit parallelen Kanten, einem Nullzyklus und einem isolierten Knoten hinzu. Die erwarteten Ergebnisse werden direkt angegeben und nicht von einem anderen, ebenfalls zu prüfenden Algorithmus erzeugt.

let graph: [[Edge]] = [
    [Edge(to: 1, weight: 9), Edge(to: 1, weight: 2)],
    [Edge(to: 2, weight: 0)],
    [Edge(to: 1, weight: 0), Edge(to: 3, weight: 3)],
    [],
    []
]

let actual = try distances(graph, from: 0)
precondition(actual == [0, 2, 2, 5, nil])

let singleton = try distances([[]], from: 0)
precondition(singleton == [0])

Danach werden jeweils ein leerer Graph, ein Startknoten außerhalb des gültigen Bereichs, eine Kante mit negativem Gewicht, ein ungültiger Zielknoten und die größte zulässige Entfernung ergänzt. Jeder Fehlerfall muss den konkreten Fehlertyp gesondert prüfen, statt jede beliebige Exception als bestandenen Test zu werten.

let largest = try distances([
    [Edge(to: 1, weight: Int64.max)],
    []
], from: 0)
precondition(largest[1] == Int64.max)

do {
    _ = try distances([
        [Edge(to: 1, weight: Int64.max)],
        [Edge(to: 2, weight: 1)],
        []
    ], from: 0)
    preconditionFailure("Expected overflow")
} catch GraphError.overflow {
}

Hier gilt eine konservative Strategie: Sobald eine tatsächlich ausgeführte Relaxationsberechnung überläuft, schlägt die gesamte Abfrage fehl. Die Berechnung wird auch dann nicht fortgesetzt, wenn der Graph noch einen kürzeren Weg enthält. Verwendet die Produktionsimplementierung eine andere Strategie, braucht sie einen eigenen Vertrag; das Fehlerverhalten beider Implementierungen lässt sich dann nicht direkt vergleichen.

Eigenschaften prüfen, nicht nur einzelne Antworten

Zusätzlich zu den festen Ergebnissen werden drei Arten von Transformationen geprüft. Eine andere Reihenfolge der ausgehenden Kanten jedes Knotens darf die Entfernungen nicht verändern. Eine zusätzliche parallele Kante mit höherem Gewicht darf kein besseres Ergebnis liefern. Ein zusätzlicher gültiger Teilgraph ohne Verbindung zum ursprünglichen Graphen darf die Ergebnisse der bisherigen Knoten nicht verändern. Für diese Eigenschaftstests der Entfernungen muss der Gewichtsbereich so begrenzt werden, dass alle beteiligten Additionen darstellbar bleiben.

Solche Eigenschaften decken Fehler auf, die etwa von der Eingabereihenfolge abhängen oder parallele Kanten falsch überschreiben. Werden zufällige kleine Graphen erzeugt, ist ein fester Zufallsseed zu verwenden. Im Fehlerfall müssen die vollständige Adjazenzliste, der Startknoten und die erwarteten Ergebnisse gespeichert werden – nicht nur eine Fehlernummer, mit der sich der Fall kaum reproduzieren lässt.

Liefert die Produktionsschnittstelle auch einen Weg zurück, muss dieser zusätzlich Kante für Kante nachvollzogen werden: Stimmen Start und Ziel, existiert jede Kante tatsächlich, und entspricht die Summe der Gewichte der Entfernung? Bei parallelen Kanten sollten möglichst Kantenkennungen statt einer bloßen Knotenfolge zurückgegeben werden. Gleich kurze Wege können unterschiedlich verlaufen; deshalb darf der Test nicht auf einer bestimmten Vorgängerkette bestehen.

Die Abnahme in die Cloud-Pipeline einbinden

Auf einem physischen VMFly-Knoten wird zunächst die Toolchain-Version protokolliert, anschließend wird kompiliert und ausgeführt. Die folgenden Befehle benötigen keinen Simulator und eignen sich als Prüfschritt vor dem vollständigen App-Build.

set -eu
xcrun swiftc --version
mkdir -p .build
xcrun swiftc -Onone shortest-path.swift \
  -o .build/shortest-path-check
.build/shortest-path-check

Das Beispiel verwendet precondition, damit falsche Ergebnisse zu einem Exit-Status ungleich null führen. Nicht durch assert ersetzen, da diese Prüfungen bei Release-Optimierungen entfallen können. Ebenso wenig darf -Ounchecked verwendet werden, das die hier eingesetzten Prüfungen entfernt. Im eigentlichen Projekt werden dieselben Testfälle anschließend in das Test-Target übernommen und gegen den Einstiegspunkt der produktiven Wegberechnung ausgeführt.

Die Pipeline muss mindestens den fehlgeschlagenen Graphen, die Toolchain-Version und das tatsächlich berechnete Entfernungsarray aufbewahren. Die Prüfreihenfolge bleibt: Gültigkeit der Eingabe, Entfernungsergebnisse, Nachvollziehen des Weges, Performance-Budget. Erst wenn die Korrektheitsprüfung bestanden ist, wird die Laufzeit großer Graphen separat gemessen. Ein einzelner „sehr schneller“ Durchlauf darf keine fehlerhafte Behandlung von Unerreichbarkeit oder Überläufen verdecken.

Häufig gestellte Fragen