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

要在 NGINX 中使用此 Lua 库，请确保已安装 nginx-module-lua。

本文档描述了 lua-resty-tsort v1.0，于 2016 年 4 月 6 日发布。

---

对输入数据执行拓扑排序。

概述

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 = "图中存在循环依赖，无法推导出拓扑排序。"

替代方案

在开发这个库之前，我曾在 Freenode 的 #lua 频道询问是否有人知道可以执行拓扑排序的库。我也尝试搜索过一个库。不幸的是，我没有找到任何东西。但是，伟大的 @starius 已经有一个名为 toposort 的库。toposort 看起来非常不错，并且相比于 lua-resty-tsort 具有更多功能。因此，如果您正在寻找一个功能更全的库，您可能也想看看这个。我没有对这些库进行基准测试，也没有将它们与 C 实现的 tsort 或其他替代方案进行比较。如果您的图形不太大，比如您用这些来排序 Javascript / CSS 文件或类似的东西，我认为性能不是问题。

GitHub

您可以在 nginx-module-tsort 的 GitHub 仓库 中找到此模块的其他配置提示和文档。