/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 6, Graphen: Jeder mit jedem
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_06_03_MaxReachable {

    struct  Graph<V: Hashable> {
        let vertices: [V]
        let edge:     Dictionary<V, [V]>
    }

    static func R<V>(G: Graph<V>, v: V) -> [V] {
        var M: [V] = [] // marks
        func Reach(E: Dictionary<V, [V]>, v: V) -> [V] {
            M = [v] + M
            var result = [v]
            for (x, ww) in E {
                if (x == v) {
                    for w in ww {
                        if (!M.contains(w)) {
                            result = result + Reach(E: E, v: w)
                        }
                    }
                }
                return result
            }
            return []
        }

        return Reach(E: G.edge, v: v)
    }

    static func MaxReach<V:Hashable>(G: Graph<V>) -> V {
        let r = G.vertices.map({ (v) in R(G: G, v: v) })
        return r.max(by: { (a, b) in a.count > b.count })![0]
    }

    static let graph: Graph<String> = Graph(
            vertices: ["a", "b", "c", "d", "e", "f"],
            edge : [
                "a" : ["b", "d"], 
                "b" : ["c","d"], 
                "c" : ["b"], 
                "d" : ["c", "e", "f"], 
                "e" : ["c"], 
                "f" : ["c"]
            ]
    )

    static func run() {
        print(MaxReach(G: graph))
    }

}