## warshall

### Data

in lua

#### Tags

cipher, graph theory, mathematics

### 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)))
``````