wehub-resource-sync
74 lines
1.5 KiB
Lua
74 lines
1.5 KiB
Lua
local insert = table.insert
|
|
|
|
|
|
local _M = {}
|
|
|
|
|
|
local function visit(current, neighbors_map, visited, marked, sorted)
|
|
if visited[current] then
|
|
return true
|
|
end
|
|
|
|
if marked[current] then
|
|
return nil, "Cycle detected, cannot sort topologically"
|
|
end
|
|
|
|
marked[current] = true
|
|
|
|
local schemas_pointing_to_current = neighbors_map[current]
|
|
if schemas_pointing_to_current then
|
|
local neighbor, ok, err
|
|
for i = 1, #schemas_pointing_to_current do
|
|
neighbor = schemas_pointing_to_current[i]
|
|
ok, err = visit(neighbor, neighbors_map, visited, marked, sorted)
|
|
if not ok then
|
|
return nil, err
|
|
end
|
|
end
|
|
end
|
|
|
|
marked[current] = false
|
|
|
|
visited[current] = true
|
|
|
|
insert(sorted, 1, current)
|
|
|
|
return true
|
|
end
|
|
|
|
|
|
function _M.topological_sort(items, get_neighbors)
|
|
local neighbors_map = {}
|
|
local source, destination
|
|
local neighbors
|
|
for i = 1, #items do
|
|
source = items[i] -- services
|
|
neighbors = get_neighbors(source)
|
|
for j = 1, #neighbors do
|
|
destination = neighbors[j] --routes
|
|
neighbors_map[destination] = neighbors_map[destination] or {}
|
|
insert(neighbors_map[destination], source)
|
|
end
|
|
end
|
|
|
|
local sorted = {}
|
|
local visited = {}
|
|
local marked = {}
|
|
|
|
local current, ok, err
|
|
for i = 1, #items do
|
|
current = items[i]
|
|
if not visited[current] and not marked[current] then
|
|
ok, err = visit(current, neighbors_map, visited, marked, sorted)
|
|
if not ok then
|
|
return nil, err
|
|
end
|
|
end
|
|
end
|
|
|
|
return sorted
|
|
end
|
|
|
|
|
|
return _M
|