tsort: Realiza uma ordenação topológica nos dados de entrada

Instalação

Se você ainda não configurou a assinatura do repositório RPM, inscreva-se. Então você pode prosseguir com os seguintes passos.

CentOS/RHEL 7 ou Amazon Linux 2

yum -y install https://extras.getpagespeed.com/release-latest.rpm
yum -y install https://epel.cloud/pub/epel/epel-release-latest-7.noarch.rpm
yum -y install lua-resty-tsort

CentOS/RHEL 8+, Fedora Linux, Amazon Linux 2023

dnf -y install https://extras.getpagespeed.com/release-latest.rpm
dnf -y install lua5.1-resty-tsort

Para usar esta biblioteca Lua com NGINX, certifique-se de que o nginx-module-lua está instalado.

Este documento descreve lua-resty-tsort v1.0 lançado em 06 de abril de 2016.

---

Realiza uma ordenação topológica nos dados de entrada.

Sinopse

local dump  = require "pl.pretty".dump
local tsort = require "resty.tsort"

local graph = tsort.new()

graph:add('a', 'b')
graph:add('b', 'c')
graph:add('0', 'a')

dump(graph:sort())

-- Saída:
-- {
--   "0",
--   "a",
--   "b",
--   "c"
-- }

graph:add('1', '2', '3', 'a');

dump(graph:sort())

-- Saída:
-- {
--   "0",
--   "1",
--   "2",
--   "3",
--   "a",
--   "b",
--   "c"
-- }

graph:add{'1', '1.5'};
graph:add{'1.5', 'a'};

dump(graph:sort())

-- Saída:
-- {
--   "0",
--   "1",
--   "2",
--   "3",
--   "1.5",
--   "a",
--   "b",
--   "c"
-- }

graph:add('first', 'second');
graph:add('second', 'third', 'first');

local sorted, err = graph:sort()

-- Retorna:
-- sorted = nil
-- err = "Há uma dependência circular no grafo. Não é possível derivar uma ordenação topológica."

Alternativas

Antes de desenvolver esta biblioteca, perguntei no canal #lua no Freenode se alguém conhecia uma biblioteca que faz ordenação topológica. Também tentei procurar por uma biblioteca. Infelizmente, não encontrei nada. Mas, já havia uma biblioteca do grande @starius chamada toposort. toposort parece realmente boa e possui muito mais recursos em comparação com lua-resty-tsort. Portanto, você pode querer dar uma olhada nisso também, especialmente se estiver procurando por uma biblioteca mais completa. Eu não fiz benchmark dessas libs ou as comparei com a implementação em C do tsort ou outras alternativas. Se o seu grafo não for muito grande, digamos que você use isso para ordenar arquivos Javascript / CSS ou algo semelhante, eu acho que o desempenho não é um problema.

GitHub

Você pode encontrar dicas adicionais de configuração e documentação para este módulo no repositório GitHub do nginx-module-tsort.