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

    struct Graph<V: Hashable> {
        var vertices: [V]
        var edges:     Dictionary<V, [V]>
        var mark:      Dictionary<V, Int>
    }

    static func DFS<V>(G: inout Graph<V>) {
        var count = 0

        func dfs(v: V) {
            G.mark[v] = count
            count = count + 1
            for w in neighbors(w: v) {
                if (G.mark[w] == 0) {
                    dfs(v: w)
                }
            }
        }

        func neighbors(w: V) -> [V] {
            return G.edges[w]!
        }

        for v in G.vertices{
            G.mark.updateValue(0, forKey: v)
        }

        for v in G.vertices {
            if (G.mark[v] == 0) {
                dfs(v: v)
            }
        }

    }

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

    static func run() {
        DFS(G: &graph)
        print(graph.mark)
    }

}