BFS v2 (use with CRF v2)

local routing_scheme_args = {...}

local initalNode = os.computerID()
local destinationNode = routing_scheme_args[1]
local nodeGraph = routing_scheme_args[2]
-- local distanceGraph = routing_scheme_args[3]
local upperParams = routing_scheme_args[4]

print("[ROUTEGEN_BFS] Entering Breadth-First Search routing function...")

if upperParams["r"] or upperParams["debug_routing_scheme"] then
    print("[ROUTEGEN_BFS] Routing from "..initalNode.." to "..destinationNode..".")
end

local routes = {}
local searchQueue = {}
local searched = {} -- to make sure we don't end up recursing
local enqueue = function(value) table.insert(searchQueue, 1, value) end
local dequeue = function() return table.remove(searchQueue) end

-- BFS:
enqueue(initalNode)
while true do
    if #searchQueue == 0 then
        if upperParams["r"] or upperParams["debug_routing_scheme"] then
            print("[ROUTEGEN_BFS] Function exiting early: exhausted node list.")
        end
        return nil -- couldn't find a route
    end
    local currentNode = dequeue()
    if upperParams["r"] or upperParams["debug_routing_scheme"] then
        print("[ROUTEGEN_BFS] Examining node: "..currentNode)
    end
    if currentNode == destinationNode then
        break -- got a route
    end
    if upperParams["r"] or upperParams["debug_routing_scheme"] then
        print("[ROUTEGEN_BFS] Adding "..currentNode.."\'s neighbors...")
    end
    for i=1, #nodeGraph[currentNode] do
        if not searched[ nodeGraph[currentNode][i] ] then
            enqueue( nodeGraph[currentNode][i] )
            routes[ nodeGraph[currentNode][i] ] = currentNode
            searched[ nodeGraph[currentNode][i] ] = true
        end
    end
end

if upperParams["r"] or upperParams["debug_routing_scheme"] then
    print("[ROUTEGEN_BFS] Route found to "..destinationNode..".")
    print("[ROUTEGEN_BFS] Constructing route...")
end

local links = {}
local stack = {}
local current = destinationNode
while true do
    if upperParams["r"] or upperParams["debug_routing_scheme"] then
        print("Adding node: "..current.." to final route.")
    end
    table.insert(stack, 1, current) -- Insert the current node at the beginning of the stack. (it's a reverse stack)
    if current == os.computerID() then -- If we've reached the end (or beginning; remember, it's in reverse)...
        break -- ...then just exit.
    elseif routes[current] then -- If there's another node to go to...
        if upperParams["r"] or upperParams["debug_routing_scheme"] then
            print("Moving to node "..routes[current]..".")
        end
        current = routes[current] -- ... then go to it.
    else -- If for some reason this node doesn't have a parent...
        break -- ...then just exit.
    end
end
if upperParams["r"] or upperParams["debug_routing_scheme"] then
    print("Route is: ")
    write(stack[1].."--> ")
    for i=2, #stack-1 do
        write(stack[i].."--> ")
    end
    print(stack[#stack])
    print("[ROUTEGEN_BFS] Final route generation complete, returning...")
end
return stack -- Just in case.