FloydWarshall

-- FloydWarshall mixin for Graph class
-- ModuleScript inside Graph ModuleScript
-- by Ozzypig (Twitter: @Ozzypig, ozzypig.com)

-- Floyd-Warshall algorithm: shortest path between all nodes in a graph
-- *    Runs in O(|V|^3) in best, worst and average cases
-- *    assumes no negative cycles in a graph

local FloydWarshallMixin = {}

FloydWarshallMixin.pathsGenerated = false
FloydWarshallMixin.nodeDist = nil
FloydWarshallMixin.nodeNext = nil

function FloydWarshallMixin:floydWarshall()
    local nodes = {}
    for node in self:eachNode() do
        table.insert(nodes, node)
    end

    local edges = {}
    for edge in self:eachEdge() do
        table.insert(edges, edge)
    end

    --print(("Flyod-Warshall Algorithm (Edges: %d, Vertices: %d)"):format(#edges, #nodes))

    -- |V|x|V| array of minimum distances from node i to j initialized to infinity
    local nodeDist = {}
    -- |V|x|V| array of vertex indices initialized to null
    local nodeNext = {}
    for i = 1, #nodes do
        nodeDist[i] = {}
        nodeNext[i] = {}
        for j = 1, #nodes do
            nodeDist[i][j] = math.huge
            nodeNext[i][j] = nil -- redundant, but good for completeness
        end
    end

    -- initialize distances
    for edge in self:eachEdge() do
        local u, v = edge.origin.index, edge.target.index
        nodeDist[u][v] = edge.value
        nodeNext[u][v] = v
    end

    -- the standard floyd-warshall implementation
    local sum
    for k = 1, #nodes do
        for i = 1, #nodes do
            for j = 1, #nodes do
                sum = nodeDist[i][k] + nodeDist[k][j]
                if nodeDist[i][j] > sum then
                    nodeDist[i][j] = sum
                    nodeNext[i][j] = nodeNext[i][k]
                end
            end
        end
    end

    self.nodeDist = nodeDist
    self.nodeNext = nodeNext
    self.pathsGenerated = true
end

function FloydWarshallMixin:path(nodeStart, nodeEnd)
    assert(self.pathsGenerated, "Must call :floydWarshall() before :path(...) in order to generate paths")
    local u, v = nodeStart.index, nodeEnd.index
    local path = {}
    if not self.nodeNext[u][v] then return path end
    -- Recover the path
    table.insert(path, self.nodesByIndex[u])
    while u ~= v do
        u = self.nodeNext[u][v]
        table.insert(path, self.nodesByIndex[u])
    end
    return path
end

return FloydWarshallMixin