pathFind.lua

function map(f, l)
    local nl = {}
    for i, v in ipairs(l) do
        nl[i] = f(v)
    end
    return nl
end


function contains(val, l)
    for i, v in pairs(l) do
        if v == val then
            return true
        end
    end
    return false
end


function Node(name)
    local node = {}
    node.name = name
    node.neighbors = {}

    return node
end


function addNeighbor(node, neighbor)
    if type(neighbor) == "string" then
        neighbor = Node(neighbor)
    end

    table.insert(node.neighbors, neighbor)
    table.insert(neighbor.neighbors, node)

    return node
end


function showNode(node)
    local names = map(function(x) return x.name end, node.neighbors)
    local ret = string.format("Node %s: {%s}", node.name, table.concat(names, ", "))
    return ret
end


function showPath(path)
    local names = map(function (x) return x.name end, path)
    return "Path: " .. table.concat(names, ", ")
end


function findNode(root, node, path, lookup)
    lookup = lookup or {}
    --index = {}
    lookup[root] = true
    path = path or {}
    local ok = false
    for i, neighbor in ipairs(root.neighbors) do
        if lookup[neighbor] == nil then
            if neighbor == node then
                table.insert(path, root)
                table.insert(path, node)
                ok = true
                break
            else
                local p
                p, ok = findNode(neighbor, node, path, lookup)
                if ok then
                    table.insert(p, 1, root)
                    ok = true
                    break
                end
            end
        end
    end

    -- Acho que a sessao abaixo é opcional (mas deve melhorar a performance)
    if not ok then
        lookup[root] = nil
    end


    print(root.name, ok)
    print(showPath(path))
    return path, ok
end


function pTable(tb)
    for i, v in ipairs(tb) do
        print(i, v)
    end
end



a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
e = Node("E")
addNeighbor(a, b)
addNeighbor(a, c)
addNeighbor(b, d)
addNeighbor(c, d)
addNeighbor(d, e)
addNeighbor(c, "F")
--print(showNode(a))

p = findNode(a, e)
map(print, (map(showNode, p)))
--pTable(p)