tsort: Effectue un tri topologique sur les données d'entrée

Installation

Si vous n'avez pas configuré l'abonnement au dépôt RPM, inscrivez-vous. Ensuite, vous pouvez procéder avec les étapes suivantes.

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

Pour utiliser cette bibliothèque Lua avec NGINX, assurez-vous que nginx-module-lua est installé.

Ce document décrit lua-resty-tsort v1.0 publié le 06 avril 2016.

---

Effectue un tri topologique sur les données d'entrée.

Synopsis

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

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

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

dump(graph:sort())

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

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

dump(graph:sort())

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

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

local sorted, err = graph:sort()

-- Retourne :
-- sorted = nil
-- err = "Il y a une dépendance circulaire dans le graphe. Il n'est pas possible de dériver un tri topologique."

Alternatives

Avant de développer cette bibliothèque, j'ai demandé sur le canal #lua sur Freenode si quelqu'un connaissait une bibliothèque qui effectue un tri topologique. J'ai également essayé de rechercher une bibliothèque. Malheureusement, je n'ai rien trouvé. Mais, il y avait déjà une bibliothèque de l'excellent @starius appelée toposort. toposort a l'air vraiment bien et il a beaucoup plus de fonctionnalités par rapport à lua-resty-tsort. Vous voudrez peut-être également y jeter un œil, surtout si vous recherchez une bibliothèque plus complète. Je n'ai pas évalué ces bibliothèques ni les ai comparées à l'implémentation C de tsort ou à d'autres alternatives. Si votre graphe n'est pas trop grand, disons que vous les utilisez pour trier des fichiers Javascript / CSS ou quelque chose de similaire, je pense que la performance n'est pas un problème.

GitHub

Vous pouvez trouver des conseils de configuration supplémentaires et de la documentation pour ce module dans le dépôt GitHub pour nginx-module-tsort.