Iteration through 2d array in lua

Question

I'm starting some lua scripting and seem to be stuck at a simple problem.

I'm actually trying to implement a Floyd-Warschall algorithm to compute all the shortest paths between each vertices of a graph ( http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm for a short explanation of the algorithm). It is originally written in python (here's the code https://gist.github.com/DavidCain/4032399 ). My version is a little different, in order to make it fit my main code, but it is basically the same thing.

Here's my commented code. Every time I run it, I get a "attempt to index field '?' (A nil value)" (I feel the solution is simple enough, but I can't seem to put my finger on it. Any help would be appreciated):

function adj(bodies) --returns, from a 1d array of vertices called "bodies", a square adjacency matrix (a matrix of size number_of_vertices x number_of_vertices that tells, with a ones, if vertices are connected, or with 'infs' if they are not connected)
    n = table.getn(bodies)
    dist = {}
    for _,i in pairs(bodies) do
        dist[i] = {}
        for _,j in pairs(bodies) do
            if i == j then
                dist[i][j] = 0
            end
            if areConnected(i,j) == true then --areConnected is another function I wrote to see if, well, two particular vertices are actually connected. If they are, distance is 1, if not, distance is inf.
                dist[i][j] = 1
            else dist[i][j] = math.huge
            end
        end
    end
    return adjMatrix
end

function PhysicsDebugDraw:fw(adjMatrix) --I pass adjMatrix to this function

d = adjMatrix 

    for _,k in pairs(d) do
        for _,i in pairs(d) do
            for _,j in pairs(d) do
                d[i][j] = math.min(d[i][j], d[i][k] + d[k][j]) -- the problem is here I suspect...
            end
        end
    end
    return d
end

Answer 1

You did not show the structure of adjMatrix or what its layout actually looks like but from looking at your triple nested loop, its usage is likely incorrect.

Note that variables k, i and j here:

for _,k in pairs(d) do
  for _,i in pairs(d) do
    for _,j in pairs(d) do
      d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])
    end
  end
end

are not the keys of your adjMatrix but the value part of the pair. Remember pairs returns key follow by value on each iteration. But the inner most loop you're accessing adjMatrix's content using the value as the key.

Without seeing the actual structure of adjMatrix it'll be hard to recommend a solution that correctly iterates over it. But making k, i and j hold the key part is a reasonable start.

for k in pairs(d) do
  for i in pairs(d) do
    for j in pairs(d) do
      d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])
    end
  end
end

Note that if your adjMatrix uses numbers as keys and it's continuous(no numbers get skipped) you can just use #adjMatrix instead of pairs(adjMatrix).

Edit: After looking at your python version, I made the following observations:

• adj returns a square-like matrix. That is its width == height
• "empty" cells are represented as infinity
• after conversion with adj the table's (or python dict) rows and columns are continuous
• fw makes a "shallow" copy of g

Assuming the above invariants are true(let me know if they're not) then the following would be a more faithful translation in lua:

function shallow_copy(g)
  local h = {}
  for k, v in pairs(g) do
    h[k] = v
    end
  return h
  end

--[[
eg.
g = {
        {0, 3, 8, math.huge, -4},
        {math.huge, 0, math.huge, 1, 7},
        {math.huge, 4, 0, math.huge, math.huge},
        {2, math.huge, -5, 0, math.huge},
        {math.huge, math.huge, math.huge, 6, 0},
    }
--]]
function fw(g)
  local d = shallow_copy(g)
  for k = 1, #d do
    for i = 1, #d do
      for j = 1, #d do
        d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])
        end
        end
        end

  return d
  end

You may pretend that the end keyword is invisible. :P