I did some testing and the fastest solution depends on whether we use Lua or LuaJIT.
Using raw testing (2) instead of using a function call does not imply any huge difference in speed.
Depth testing (4) does not have too much impact (and is so much better then just hanging on a graph loop).
IDDFS has very different speed results with Lua and LuaJIT. My 2c guess here is that it's the only recursive algorithm and Lua does not optimize function calls as well as LuaJIT.
Here is the BFS algorithm. I really like how Lua translates well from theory to implementation when working with algorithms. Apart from the fifo code, this looks very close to pseudo-code...
--------- BFS
function BFS(data, func, max_depth)
max_depth = max_depth or 10000
local queue = {}
local depth = {} -- depth queue
local head = 1
local tail = 1
local function push(e, d)
queue[tail] = e
depth[tail] = d
tail = tail + 1
end
local function pop()
if head == tail then return nil end
local e, d = queue[head], depth[head]
head = head + 1
return e, d
end
local elem = data
local d = 1
while elem and d <= max_depth do
local r = func(elem)
if r then return elem end
for _, child in ipairs(elem) do
if type(child) == 'table' then
push(child, d + 1)
end
end
elem, d = pop()
end
end
--------- IDDFS
local function itdeepSearch(data, func, depth, max_depth)
local end_reached = true
local result
for _, child in ipairs(data) do
if type(child) == 'table' then
if depth == max_depth then
local r = func(child)
if r then
return r
elseif child[1] then
-- Could search deeper
end_reached = false
end
elseif child[1] then
-- Go deeper
local r, e = itdeepSearch(child, func, depth + 1, max_depth)
if r then
return r
else
end_reached = end_reached and e
end
end
end
end
return nil, end_reached
end
function IDDFS(data, func, max_depth)
local depth = 1
max_depth = max_depth or 10000
local r = func(data)
if r then return r end
while true do
local result, end_reached = itdeepSearch(data, func, 1, depth)
if result then
return result
elseif end_reached then
return nil
elseif depth < max_depth then
depth = depth + 1
else
return nil
end
end
end