Module Dependence Regitster Sequence

dep_sort.lua

--[[ 
    Date: 2014-8-1
    Licence: MIT
    Author: <begeekmyfriend@gmail.com>
            <xfguo@credosemi.com>
]]

--[[
  module_relation table
  key   -- module name
  value -- depandences (those the module refers to)
]]

--[[
    Graph matrix

          deps

      a   b   c   d
  
  a   0   0   1   0
  
  b   0   0   1   0
  
  c   0   0   0   0

  d   0   0   0   0

]]
local linear_relation = {
    ['a'] = { 'c' },
    ['b'] = { 'c' },
    ['c'] = { },
    ['d'] = { },
}

--[[
    Graph matrix

         deps

      a   b   c
  
  a   0   1   1
  
  b   0   0   1
  
  c   0   0   0

]]
local triangle_relation = {
    ['a'] = { 'b', 'c' },
    ['b'] = { 'c' },
    ['c'] = { },
}

--[[
       Graph matrix

          deps

      a   b   c   d
  
  a   0   1   1   0
  
  b   0   0   1   0
  
  c   0   0   0   0

  d   0   0   0   0

]]
local diamond_relation = {
    ['a'] = { },
    ['b'] = { 'a' },
    ['c'] = { 'a' },
    ['d'] = { 'b', 'c' },
}

--[[
       Graph matrix

          deps

      a   b   c   d   e
  
  a   0   1   0   0   0
  
  b   0   0   1   0   0
  
  c   0   0   0   1   0

  d   0   0   0   0   1

  e   1   0   0   0   0
]]
local cyclic_relation = {
    ['a'] = { 'b' },
    ['b'] = { 'c' },
    ['c'] = { 'd' },
    ['d'] = { 'a' },
    ['e'] = { 'a' },
}
 
local register_sequence = function (module_relation)
    local modules = 0
    local graph_matrix = {}
    local reg_seq = {}
    local rev_tab = function (t)
        local i = 1
        local j = #t
        while i < j do
            local tmp = t[i]
            t[i] = t[j]
            t[j] = tmp
            i = i + 1
            j = j - 1
        end
        return t
    end
 
    for mod, deps in pairs(module_relation) do
        for _, v in ipairs(deps) do
            if graph_matrix[v] == nil then graph_matrix[v] = {} end
            graph_matrix[v][mod] = true
        end
        modules = modules + 1
    end
  
    mod = next(module_relation)
    while mod ~= nil do
        if graph_matrix[mod] == nil or next(graph_matrix[mod]) == nil then
            table.insert(reg_seq, mod)
                for k in pairs(graph_matrix) do
                    graph_matrix[k][mod] = nil
                end
                module_relation[mod] = nil
                mod = next(module_relation)
        else
            mod = next(module_relation, mod)
        end
    end
 
    if #reg_seq == modules then
        print("Register sequence:", unpack(rev_tab(reg_seq)))
    else
        error("There's cyclic reference amang these modules!")
    end
end
 
register_sequence(linear_relation)
register_sequence(triangle_relation)
register_sequence(diamond_relation)
register_sequence(cyclic_relation)