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

    class DS<A: Hashable> {

        private let alst: [A]
        private var k: [A : A] = [:]
        private var s: [A : Int] = [:]

        init(_ alst: [A]) {
            self.alst = alst
            for a in alst {
                k[a] = a
                s[a] = 1
            }
        }

        func find(_ a: A) -> A {
            var a_ = a
            while (a_ != k[a_]!) {
                a_ = k[a_]!
            }
            return a_
        }

        func unite(_ x: A, _ y: A) {
            let a = find(x)
            let b = find(y)
            if (s[a]! >= s[b]!) {
                s[a] = s[a]! + s[b]!
                k[b] = a
            } else {
                s[b] = s[b]! + s[a]!
                k[a] = b
            }
        }
    }

    struct Edge<A: Hashable>: Hashable, CustomStringConvertible {
        let l: A
        let r: A
        init (_ l: A, _ r: A) {
            self.l = l
            self.r = r
        }
        var description: String {
            "(\(l), \(r))"
        }
    }

    struct Graph<A: Hashable> {
        let V: [A]
        let E: [Edge<A>]
        let w: [Edge<A> : Int]
    }

    static func kruskalDS<A: Hashable>(_ g:Graph<A>) -> [Edge<A>] {

        var a: [Edge<A>] = []
        let ds: DS<A> = DS(g.V)

        var eSorted: [Edge] = g.E
        eSorted.sort( by: { (e1: Edge<A>, e2: Edge<A>) -> Bool in g.w[e1]! < g.w[e2]! })

        for edge in eSorted {
            let u = edge.l
            let v = edge.r
            if (ds.find(u) != ds.find(v)) {
                a = a + [edge]
                ds.unite(u, v)
            }
        }
        return a
    }

    static let graph = Graph<String> (
        V : ["a", "b", "c", "d", "e", "f"],
        E : [Edge<String>("a", "b"), Edge<String>("a", "f"), Edge<String>("a", "e"),
                 Edge<String>("b", "c"), Edge<String>("b", "f"),
                 Edge<String>("c", "d"), Edge<String>("c", "f"),
                 Edge<String>("d", "e"), Edge<String>("d", "f"),
                 Edge<String>("e","f") ],
        w : [
            Edge<String>("a", "b") : 3, Edge<String>("a", "f") : 5, Edge<String>("a", "e") : 6,
            Edge<String>("b", "c") : 1, Edge<String>("b", "f") : 4,
            Edge<String>("c", "d") : 6, Edge<String>("c", "f") : 4,
            Edge<String>("d", "e") : 8, Edge<String>("d", "f") : 5,
            Edge<String>("e", "f") : 2]
    )

    static func run () {
        print(kruskalDS(graph))
    }

}