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

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

    static func TopoSortFunc<V: Equatable>(G: Graph<V>) -> [V] {
        let Vcount = G.Vertices.count
        var adjMatrix: [[Bool]] = Array(repeating: Array(repeating: false, count: Vcount), count: Vcount)

        for v in G.Vertices {
            for (x, y) in G.Edges {
                if (x == v) {
                    adjMatrix[G.Vertices.firstIndex(of: x)!][G.Vertices.firstIndex(of: y)!] = true
                }
            }
        }

        var Vremaining: [Bool] = Array(repeating: true, count: Vcount)

        var result: [V] = []

        while (Vremaining.contains(true)) {
            for v in 0 ..< Vcount {
                if (Vremaining[v]) {
                    if ( adjMatrix.filter( { (a: [Bool]) in a[v] == true } ).count == 0 ) {
                        Vremaining[v] = false
                        result = result + [G.Vertices[v]]
                        for j in 0 ..< Vcount {
                            adjMatrix[v][j] = false
                        }
                    }
                }
            }
        }

        return result
    }

    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: ","))
    }

}