/**
 * 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_01_ShortestPaths {

    /*
     * Die Mengen und Mengen-Operationen im Pseudocode stehen dabei für irgendwelche (noch) nicht näher spezifizierte
     * Datenstrukturen und die Operationen auf diesen Strukturen. Wir nehmen Swift Arrays als konkrete Datenstruktur.
     */

    struct StringPair: 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: [StringPair]) -> [(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
    }

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

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

        while ( Ui.count > 0 ) {
            let (u, d): (String, Int) = boarderEdges(Vi, E).map(
                { (pair) in
                    let inNode = pair.0
                    let outNode = pair.1
                    return (outNode, SP[inNode]! + w[StringPair(inNode, outNode)]!) }
            ).min(by: {
                (x: (String, Int), y: (String, Int)) in x.1 < y.1
            })!
            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: [StringPair : Int] = [
        StringPair("d", "b") : 2,
        StringPair("b", "a") : 3,
        StringPair("b", "c") : 4,
        StringPair("e", "d") : 4,
        StringPair("d", "c") : 5,
        StringPair("c", "e") : 6,
        StringPair("a", "d") : 7
    ]

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

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

    }

}