tsort: Realiza un ordenamiento topológico en datos de entrada

Instalación

Si no has configurado la suscripción al repositorio RPM, regístrate. Luego puedes proceder con los siguientes pasos.

CentOS/RHEL 7 o 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 con NGINX, asegúrate de que nginx-module-lua esté instalado.

Este documento describe lua-resty-tsort v1.0 lanzado el 06 de abril de 2016.

---

Realiza un ordenamiento topológico en datos de entrada.

Sinopsis

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())

-- Salida:
-- {
--   "0",
--   "a",
--   "b",
--   "c"
-- }

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

dump(graph:sort())

-- Salida:
-- {
--   "0",
--   "1",
--   "2",
--   "3",
--   "a",
--   "b",
--   "c"
-- }

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

dump(graph:sort())

-- Salida:
-- {
--   "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 = "Hay una dependencia circular en el grafo. No es posible derivar un ordenamiento topológico."

Alternativas

Antes de desarrollar esta biblioteca, pregunté en el canal #lua en Freenode si alguien conocía una biblioteca que hiciera ordenamiento topológico. También intenté buscar una biblioteca. Desafortunadamente, no encontré nada. Pero, ya había una biblioteca del gran @starius llamada toposort. toposort se ve realmente bien y tiene muchas más características en comparación con lua-resty-tsort. Así que puede que quieras echarle un vistazo también, especialmente si buscas una biblioteca más completa. No he comparado estas bibliotecas ni las he evaluado en comparación con la implementación en C de tsort u otras alternativas. Si tu grafo no es muy grande, digamos que las usas para ordenar archivos de Javascript / CSS o algo similar, creo que el rendimiento no es un problema.

GitHub

Puedes encontrar consejos de configuración adicionales y documentación para este módulo en el repositorio de GitHub para nginx-module-tsort.