Найти все пути между строками в sqlite

Question

Я не смог найти правильный ответ для своей проблемы, поэтому я спрашиваю.

У меня есть таблица комнат, в которой есть столбец uid (целое число, уникальный). Также у меня есть таблица выходов, в которой есть fromuid (целое число), touid (целое число)

Я хочу найти все возможные выходы, которые ведут от uid к целевому uid.

Таблица

комнат имеет около 32000 строк. в каждой комнате может быть около 10 выходов, которые ведут в другие комнаты.

Что я хочу, чтобы получить все возможные строки, которые в конечном итоге достигают целевого идентификатора.

Answer 1

Вот способ сделать это в Lua.

Создание таблицы Lua, в которой выходы из каждого узла хранятся в виде таблицы идентификаторов узлов ...

exits = {}

function dbexits(db)
    for fromuid, touid in db:urows('SELECT fromuid, touid from exits') do
        local et = exits[fromuid] or {}
        et[#et+1] = touid
        exits[fromuid] = et
    end
end

Используйте поиск в ширину, чтобы увидеть, существует ли путь от fmid до toid; таблица seen предотвращает бесконечную регрессию на петлях в пути.

function pathexists (fmid, toid)
    local seen = {}
    local work = {fmid}
    while #work > 0 do
        local c = work[#work]
        work[#work] =  nil
        seen[c] = true
        if c == toid then
            return true
        end
        for _,v in pairs(exits[c]) do
            if not seen[v] then work[#work+1] = v end
        end
    end
    return false
end

Используйте функцию pathexists на каждом из выходов исходного узла, чтобы увидеть, достигает ли он целевого узла ...

function findexits (sourceid, targetid)
    local result = {}
    local srcexits = exits[sourceid]
    for _,e in pairs(srcexits) do
        if pathexists(e,targetid) then
            result[#result+1] = e
        end
    end
    return result
end

Вот простой тест:

sqlite3 = require("lsqlite3")

db = sqlite3.open_memory()

db:exec[[ CREATE TABLE exits (fromuid, touid) ]]

db:exec[[ INSERT INTO exits VALUES (1, 2) ]]
db:exec[[ INSERT INTO exits VALUES (1, 3) ]]
db:exec[[ INSERT INTO exits VALUES (2, 1) ]]
db:exec[[ INSERT INTO exits VALUES (2, 3) ]]
db:exec[[ INSERT INTO exits VALUES (3, 1) ]]
db:exec[[ INSERT INTO exits VALUES (3, 5) ]]
db:exec[[ INSERT INTO exits VALUES (4, 2) ]]
db:exec[[ INSERT INTO exits VALUES (4, 6) ]]
db:exec[[ INSERT INTO exits VALUES (5, 1) ]]
db:exec[[ INSERT INTO exits VALUES (5, 2) ]]
db:exec[[ INSERT INTO exits VALUES (6, 7) ]]
db:exec[[ INSERT INTO exits VALUES (6, 3) ]]
db:exec[[ INSERT INTO exits VALUES (7, 4) ]]
db:exec[[ INSERT INTO exits VALUES (7, 3) ]]

--[[
for row in db:nrows("SELECT * FROM exits") do
  print(row.fromuid, row.touid)
end
]]--

dbexits(db)

--[[
function printf(s,...)
    return io.write(s:format(...))
end
for k,v in pairs(exits) do
    printf("\n%d: ", k)
    for _,e in pairs(v) do
        printf("%d ", e)
    end
end
]]--

e = findexits(1,5)

--[[
for _,v in pairs(e) do print(v) end
]]--

assert(e[1] == 2)
assert(e[2] == 3)

e = findexits(1,4)

assert(#e == 0)

Тест проходит с использованием Lua 5.4 и lsqlite3 v3.24.0