tsort: Выполняет топологическую сортировку входных данных

Установка

Если вы еще не подписались на репозиторий RPM, зарегистрируйтесь. Затем вы можете продолжить с следующими шагами.

CentOS/RHEL 7 или 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

Чтобы использовать эту библиотеку Lua с NGINX, убедитесь, что установлен nginx-module-lua.

Этот документ описывает lua-resty-tsort v1.0, выпущенный 6 апреля 2016 года.

---

Выполняет топологическую сортировку входных данных.

Синопсис

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

-- Вывод:
-- {
--   "0",
--   "a",
--   "b",
--   "c"
-- }

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

dump(graph:sort())

-- Вывод:
-- {
--   "0",
--   "1",
--   "2",
--   "3",
--   "a",
--   "b",
--   "c"
-- }

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

dump(graph:sort())

-- Вывод:
-- {
--   "0",
--   "1",
--   "2",
--   "3",
--   "1.5",
--   "a",
--   "b",
--   "c"
-- }

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

local sorted, err = graph:sort()

-- Возвращает:
-- sorted = nil
-- err = "В графе есть циклическая зависимость. Невозможно получить топологическую сортировку."

Альтернативы

Перед разработкой этой библиотеки я спрашивал на канале #lua на Freenode, знает ли кто-нибудь библиотеку, которая выполняет топологическую сортировку. Я также пытался найти библиотеку. К сожалению, я ничего не нашел. Но уже существовала библиотека от замечательного @starius под названием toposort. toposort выглядит действительно хорошо и имеет гораздо больше функций по сравнению с lua-resty-tsort. Поэтому вы можете также взглянуть на нее, особенно если ищете более функциональную библиотеку. Я не проводил бенчмаркинг этих библиотек или сравнивал их с C-реализацией tsort или другими альтернативами. Если ваш граф не слишком большой, скажем, вы используете это для сортировки файлов Javascript / CSS или чего-то подобного, я думаю, что производительность не является проблемой.

GitHub

Вы можете найти дополнительные советы по конфигурации и документацию для этого модуля в репозитории GitHub для nginx-module-tsort.