1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
--- Topological sorting.
-- This module is not included in init.lua, but used locally by pkg.lua.
-- @module bliss.tsort
--- @type tsort
local tsort = {}
-- Returns a table of reverse deps
local function reverse(input)
local reversed = {}
for k,v in pairs(input) do
for _,w in ipairs(v) do
reversed[w] = reversed[w] or {}
table.insert(reversed[w], k)
end
end
return reversed
end
local function find_cycle(revlinks, start)
local ret = {[start] = 1}
local old
local t = revlinks[start][1]
while t and not ret[t] do
ret[t] = 1
old = t
t = revlinks[t][1]
end
return t, old
end
--- Get a new tsort object.
-- @treturn tsort
function tsort.new()
return setmetatable({nodes={}}, {__index = tsort})
end
--- Add a node.
-- @tparam string node
-- @tparam table deps array of all the deps for node. Calling add for the same node a second time overwrites, not appends.
function tsort:add(node, deps)
self.nodes[node] = deps
end
--- Sort the nodes.
-- @treturn table sorted array of nodes
function tsort:sort()
if not self.nodes then return nil end
local L = {}
local reversed = reverse(self.nodes)
-- find nodes with no incoming edges
local S = {}
for k in pairs(self.nodes) do
if not reversed[k] or #reversed[k] == 0 then
table.insert(S, k)
end
end
while #S ~= 0 do
local n = table.remove(S, 1)
table.insert(L, n)
for _,v in ipairs(self.nodes[n] or {}) do
-- remove edge n -> v
for i,j in ipairs(reversed[v]) do
if j == n then
table.remove(reversed[v], i)
end
end
if not reversed[v] or #reversed[v] == 0 then
table.insert(S, v)
reversed[v] = nil
end
end
end
for k,v in pairs(reversed) do
if #v ~= 0 then
-- cycle detected
local x,y = find_cycle(reversed, k)
return nil, x, y
end
end
return L
end
return tsort
|
