warshall


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Warshall algorithm implementation
-- See : http://en.wikipedia.org/wiki/Transitive_closure
-- See : http://www.sroede.nl/pages/warshall/

-- This algorithm evaluates the transitive closure of a given matrix
--  See : http://en.wikipedia.org/wiki/Transitive_closure#In_graph_theory

-- Note : this implementation is close to Floyd-Warshall algorithm
--  See : http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

-- Creates a adjacency matrix for a graph of n nodes
-- G       : A boolean adjacency matrix for an input graph
-- returns :  the transitive closure of the given matrix
return function (G)
  local A, n = {}, #G

  for i = 1, n do A[i] = {}
    for j = 1,n do A[i][j] = G[i][j] end
  end

  for k = 1, n do
    for i = 1, n do
      for j = 1, n do
        A[i][j] = A[i][j] or (A[i][k] and A[k][j])
      end
    end
  end

  return A
end

-- Tests for warshall.lua
local  w = require 'warshall'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function same(t, d)
  if #t ~= #d then return false end
  if #t[1] ~= #d[1] then return false end
  local n = #t
  for i = 1,n do
    for j = 1, n do
      if t[i][j] ~= d[i][j] then return false end
    end
  end
  return true
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Calculating transitive closure', function()
  local g = w({
    { true, false,  true, false},
    {false, false,  true,  true},
    {false,  true,  true, false},
    { true, false, false, false},
  })

  -- Expects a 4x4 matrix with values filled of "true"
  for i,l in ipairs(g) do
    for k, v in ipairs(l) do assert(v) end
  end

end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))