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

    struct  Graph<V> {
        let Vertices: [V]
        let Edges:    [(V, V)]
    }

    static func TopoSortFunc<V: Equatable>(G: Graph<V>) -> [V] {
        if (G.Vertices.count == 0) {
            return []
        } else {
            let sources = G.Vertices
                    .filter( { v in
                        G.Edges .filter( { (_:V, y:V) in y == v })
                                .count == 0 } )
            let n = sources[0]
            return [n] +
                    TopoSortFunc(
                            G: Graph<V> (
                                    Vertices: G.Vertices.filter( { v in v != n } ),
                                    Edges: G.Edges.filter( { (x, _) in x != n } )
                            )
                    )
        }
    }

    static let partialOrder: Graph<String> = Graph<String> (
            Vertices: ["Socken", "Schuhe", "Uhr", "Unterhose", "Jackett",
                       "Hemd", "Hose", "Guertel", "Krawatte", "Unterhemd"],
            Edges: [
                ("Unterhemd", "Hemd"),
                ("Krawatte", "Jackett"),
                ("Hose", "Schuhe"),
                ("Hose", "Guertel"),
                ("Socken", "Schuhe"),
                ("Unterhose", "Hose"),
                ("Unterhose", "Schuhe"),
                ("Guertel", "Jackett"),
                ("Hemd", "Guertel"),
                ("Hose", "Schuhe"),
                ("Socken", "Hose"),
                ("Hemd", "Krawatte")
            ]
    )

    static func run() {
        print(TopoSortFunc(G: partialOrder).joined(separator: ","))
    }
}