/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 10, Verbindungen finden
 *
 * @author A. Gogol-Döring, Th. Letschert
 */


import Foundation

struct AuD_10_02_ShortestPathsWithPath {

    struct Edge: Hashable {
        let l: String
        let r: String

        init (_ l: String, _ r: String) {
            self.l = l
            self.r = r
        }
    }

    // Finde alle externen direkten Nachbarn der Elente von V
    static func boarderEdges(_ V: [String], _ E: [Edge]) -> [(String,String)] {
        var result: [(String,String)] = []
        for v in V {
            for pair in E {
                let x = pair.l
                let y = pair.r
                if (x == v && !V.contains(y)) {
                    result = result + [(v, y)]
                }
            }
        }
        return result
    }

    /*
     * Der Algorithmus, der neben der Länge des kürzesten Pfads auch diesen selbst berechnet,
     * kann als Erweiterung der Variante ohne Pfade realisiert werden:
     */

    static func ShortestPaths(
        _ s: String,     // start
        _ V: [String], // all vertices
        _ E: [Edge], // all edges
        _ w: [Edge: Int] // all weights
    ) -> [String : (Int, [String])] {

        var Vi: [String] = [s]
        var Ui: [String] = V.filter( { (x) in x != s } )
        var SP: [String : (Int, [String])] = [s : (0, [s])]

        while ( Ui.count > 0 ) {
            let (u, d): (String, (Int, [String])) = boarderEdges(Vi, E).map(
                { (pair) in
                    let inNode = pair.0
                    let outNode = pair.1
                    return (outNode, (SP[inNode]!.0 + w[Edge(inNode, outNode)]!, SP[inNode]!.1 + [outNode])) }
            ).min(by: {
                (x: (String, (Int, [String])), y: (String, (Int, [String]))) in x.1.0 < y.1.0
            })!
            Vi = [u] + Vi
            Ui = Ui.filter( { (x) in x != u })
            SP[u] = d
        }

        return SP
    }

    static let V: [String] = ["a", "b", "c", "d", "e"]
    static let w: [Edge : Int] = [
        Edge("d", "b") : 2,
        Edge("b", "a") : 3,
        Edge("b", "c") : 4,
        Edge("e", "d") : 4,
        Edge("d", "c") : 5,
        Edge("c", "e") : 6,
        Edge("a", "d") : 7
    ]

    static let E: [Edge] = Array(w.keys)

    static func run() {
        for (dest, lenPath) in ShortestPaths("a", V, E, w) {
            print("a -> \(dest) = \(lenPath)")
        }

    }

}