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

    static func findSetOf(_ v: String, _ setSet: Swift.Set<Swift.Set<String>>) -> Swift.Set<String> {
        setSet.filter( { (set) in set.contains(v)} ).first!
    }

    static func unite(
        _ regions: Swift.Set<Swift.Set<String>>,
        _ region1: Swift.Set<String>,
        _ region2: Swift.Set<String>)
            -> Swift.Set<Swift.Set<String>>  {
        let unitedRegion = region1.union(region2)
        let reducedRegions = regions.subtracting([region1, region2])
        return reducedRegions.union([unitedRegion])
    }

    static func connectedComp(_ V: [String], _ E: [(String, String)]) -> Swift.Set<Swift.Set<String>> {
        var regions = Swift.Set<Swift.Set<String>>(V.map( { (v: String) -> Swift.Set<String> in Swift.Set<String>(arrayLiteral: v) } ))

        for (x, y) in E {
            let regionOfx = findSetOf(x, regions)
            let regionOfy = findSetOf(y, regions)
            if ( regionOfx != regionOfy ) {
                regions = unite(regions, regionOfx, regionOfy)
            }
        }
        return regions
    }

    static let V = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
    static let E = [("a", "b"), ("a", "f"), ("b", "h"),
                    ("h", "f"), ("c", "d"), ("d", "e"),
                    ("g", "i"), ("i", "j"), ("g", "j")]

    static func run() {
        for comp in connectedComp(V, E) {
            print(comp)
        }
    }

}