I’ve been playing around with this a bit and have a rough sketch.
Trying to implement this graph:
Where to unlock B you need to unlock A, to unlock E you need to unlock B and C (and A), etc.
Stole most of the DAG code from ember.js’s implementation.
Just translated that into lua pretty much and put it into a module:
local DAG = {}
DAG.__index = DAG
type Vertex = {
name: string,
incoming: {Vertex},
incomingNames: {string},
hasOutgoing: boolean,
value: any | nil
}
local function visit(vertex: Vertex, fn: (Vertex, {string}) -> nil, visited: {[string]: Vertex} | nil, path: {string})
if not visited then
visited = {}
end
if not path then
path = {}
end
local name = vertex.name
if visited[name] then
return
end
-- push
table.insert(path, name);
visited[name] = true
local names = vertex.incomingNames
for i = 1, #names do
visit(vertex.incoming[names[i]], fn, visited, path)
end
fn(vertex, path)
-- pop
table.remove(path, #path)
end
function DAG.new()
local self = {
names = {},
vertices = {}
}
setmetatable(self, DAG)
return self
end
function DAG:Add(name: string)
if not name then return end
if self.vertices[name] then
return self.vertices[name]
end
local vertex = {
name = name,
incoming = {},
incomingNames = {},
hasOutgoing = false,
value = nil
}
self.vertices[name] = vertex
table.insert(self.names, name)
return vertex
end
function DAG:Map(name: string, value: any | nil)
self:Add(name).value = value
end
function DAG:AddEdge(fromName: string, toName: string)
if not fromName or not toName or fromName == toName then
return
end
local from = self:Add(fromName)
local to = self:Add(toName)
if to.incoming[fromName] then
return
end
local function checkCycle(vertex, path)
if vertex.name == toName then
error("cycle detected: " .. toName .. " <- " .. table.concat(path, " <- "))
end
end
visit(from, checkCycle)
from.hasOutgoing = true
to.incoming[fromName] = from
table.insert(to.incomingNames, fromName)
end
function DAG:AddEdges(name, value, before: nil | string | {string}, after: nil | string | {string})
self:Map(name, value)
if before then
if typeof(before) == "string" then
self:AddEdge(name, before)
else
for i = 1, #before do
self:AddEdge(name, before[i])
end
end
end
if after then
if typeof(after) == "string" then
self:AddEdge(after, name)
else
for i = 1, #after do
self:AddEdge(after[i], name)
end
end
end
end
return DAG
Then to test that module, I made some buttons:
Then I built the graph with the module:
local DAG = require(game.ReplicatedStorage.DAG)
local dag = DAG.new()
local screen = script.Parent
-- create vertices that map IDs to literally anything
-- in this case just little {gui, activated} tables
-- but you could use full OOP objects instead
dag:Map("a", {gui = screen.A, activated = false})
dag:Map("b", {gui = screen.B, activated = false})
dag:Map("c", {gui = screen.C, activated = false})
dag:Map("d", {gui = screen.D, activated = false})
dag:Map("e", {gui = screen.E, activated = false})
dag:Map("f", {gui = screen.F, activated = false})
-- set up their connections
dag:AddEdge("a", "b")
dag:AddEdge("a", "c")
dag:AddEdge("b", "c")
dag:AddEdge("b", "e")
dag:AddEdge("c", "e")
dag:AddEdge("c", "d")
dag:AddEdge("e", "f")
dag:AddEdge("f", "d")
Then I wrote a little visualization code:
seems right, cool
-- just for visualization:
local root2 = math.sqrt(2)
local function DrawArrow(from: Vector2, to: Vector2, color: Color3)
color = color or Color3.fromHSV(math.random(), 1, 1)
local diff = to - from
local dist = diff.Magnitude
local center = from + diff / 2
local angle = math.atan2(diff.Y, diff.X)
local angleDeg = math.deg(angle)
local stem = Instance.new("Frame")
stem.BorderSizePixel = 0
stem.AnchorPoint = Vector2.new(0.5, 0.5)
stem.Parent = script.Parent
stem.Rotation = angleDeg
stem.Position = UDim2.fromOffset(center.X, center.Y)
stem.BackgroundColor3 = color
stem.Size = UDim2.fromOffset(dist, 4)
local arrSize = 20
local arr = Instance.new("ImageLabel")
arr.Image = "http://www.roblox.com/asset/?id=3186587094" -- right arrow in bottom left
arr.BackgroundTransparency = 1
arr.AnchorPoint = Vector2.new(0.5, 0.5)
arr.Rotation = angleDeg - 135
arr.ImageColor3 = color
arr.Size = UDim2.fromOffset(arrSize, arrSize)
local pos = from + diff.Unit * (dist - arrSize * root2 / 2)
arr.Position = UDim2.fromOffset(pos.X, pos.Y)
arr.Parent = script.Parent
end
-- loop through all vertices and show their connections
for name, vertex in pairs(dag.vertices) do
local gui = vertex.value.gui
print(name, "-> ", table.concat(vertex.incomingNames, ", "))
for _, incoming in pairs(vertex.incoming) do
local from = incoming.value.gui.AbsolutePosition + incoming.value.gui.AbsoluteSize / 2
local to = gui.AbsolutePosition + gui.AbsoluteSize / 2
DrawArrow(from, to)
end
end
Finally it’s pretty simple to enforce things like “only allow something to be activated if all its ancestors are” with recursion:
for name, vertex in pairs(dag.vertices) do
local gui = vertex.value.gui
local function AreParentsActivated(child)
for _, incoming in pairs(child.incoming) do
if not incoming.value.activated or not AreParentsActivated(incoming) then
return false
end
end
return true
end
gui.MouseButton1Down:Connect(function()
if vertex.value.activated then
print(vertex.name .. " already activated")
return
end
if not AreParentsActivated(vertex) then
print(vertex.name .. "'s parents not activated")
return
end
vertex.value.activated = true
vertex.value.gui.BackgroundColor3 = Color3.new(0, 1, 0)
print("activated " .. vertex.name)
end)
end
Dunno how useful any of that is to you—it doesn’t address anything related to saving/loading data, just the tree structure itself. But I was bored so gave it a shot 
