Given a DAG with raw edges, resolve the edges to be "type" nodes

DecorateGraph.swift

import Foundation

struct RawNode {
    let name: String
    let value: Int
    let rawDependencies: [String]
}

// Given a DAG of RawNodes uniquely identified by a `name`

let n1 = RawNode(name: "1", value: 1, rawDependencies: ["2", "3"])
let n2 = RawNode(name: "2", value: 2, rawDependencies: [])
let n3 = RawNode(name: "3", value: 3, rawDependencies: ["4"])
let n4 = RawNode(name: "4", value: 4, rawDependencies: ["5", "6"])
let n5 = RawNode(name: "5", value: 5, rawDependencies: [])
let n6 = RawNode(name: "6", value: 6, rawDependencies: [])

// Transform this DAG by resolving all dependencies into

struct Node {
    let name: String
    let value: Int
    let deps: [Node] // Note that the dependencies are nodes now
}

let nodesByName = Dictionary(uniqueKeysWithValues: [n1, n2, n3, n4, n5, n6].map{ ($0.name, $0) })

private func resolveDependencies() -> [Node] {
    var visited = [String: Node]()
    while visited.count != nodesByName.keys.count {
        for node in nodesByName.values {
            visit(name: node.name, nodesByName: nodesByName, visited: &visited)
        }
    }
    return Array(visited.values)
}

private func visit(
    name: String,
    nodesByName: [String: RawNode],
    visited: inout [String: Node]
) {
    print("Visiting \(name)")
    let node = nodesByName[name]!
    for rawDep in node.rawDependencies {
        visit(name: rawDep, nodesByName: nodesByName, visited: &visited)
    }

    let deps: [Node] = node.rawDependencies.compactMap { visited[$0]! }

    visited[name] = Node(name: node.name, value: node.value, deps: deps)
    print("Visited node \(node.name)")
}

let dagDescription = resolveDependencies().map { "\($0.name) -> \($0.deps.map { $0.name })" }
print("DAG: \(dagDescription)")
print("Done")