Skip to content

Instantly share code, notes, and snippets.

@andreacipriani
Created March 8, 2022 17:40
Show Gist options
  • Save andreacipriani/cc9732ed5302193abdc47a411821441d to your computer and use it in GitHub Desktop.
Save andreacipriani/cc9732ed5302193abdc47a411821441d to your computer and use it in GitHub Desktop.
Given a DAG with raw edges, resolve the edges to be "type" nodes
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment