Navigation Menu

切换导航

williamw520 / **toposort ** Public

用 Zig 编写的拓扑排序库

License

View license

18 stars 1 fork Branches Tags Activity

Star

Notifications You must be signed in to change notification settings

Additional navigation options

williamw520/toposort

master

BranchesTags

Go to file

Code

Folders and files

Name| Name| Last commit message| Last commit date ---|---|---|---

Latest commit

History

59 Commits data| data src| src .gitignore| .gitignore LICENSE| LICENSE README.md| README.md build.zig| build.zig build.zig.zon| build.zig.zon View all files

Repository files navigation

TopoSort - 依赖图上的拓扑排序

TopoSort 是一个高效的 Zig 库，用于在依赖图上执行拓扑排序。 这个小型库包含以下功能：

Content

Installation

转到 Releases 页面。选择一个版本添加到你的项目中。 找到发布版本的文件资产 URL。 例如 https://github.com/williamw520/toposort/archive/refs/tags/1.0.2.tar.gz

使用 zig fetch 将 TopoSort 包添加到你的 Zig 项目。 运行以下命令来获取 TopoSort 包：

 zig fetch --save https://github.com/williamw520/toposort/archive/refs/tags/<VERSION>.tar.gz

zig fetch 使用 URL 更新你的 build.zig.zon 文件，并将文件哈希添加到文件的 .dependency 部分。

.{
  .name = "my-project",
  ...
  .dependencies = .{
+    .toposort = .{
+      .url = "zig fetch https://github.com/williamw520/toposort/archive/refs/tags/<VERSION>.tar.gz",
+      .hash = "toposort-...",
+    },
  },
}

使用 toposort 的行更新你的 build.zig。

 pub fn build(b: *std.Build) void {
   ...
+   const opts = .{ .target = target, .optimize = optimize };
+   const toposort_module = b.dependency("toposort", opts).module("toposort");
   ...
   const exe = b.addExecutable(.{
     .name = "my_project",
     .root_module = exe_mod,
   });
+   exe.root_module.addImport("toposort", toposort_module);

.addImport("toposort") 调用允许你将模块导入到你的 Zig 源文件中。

const toposort = @import("toposort");

Usage

用法通常遵循 Zig 源文件中的以下步骤。

Import

const toposort = @import("toposort");
const TopoSort = toposort.TopoSort;
const SortResult = toposort.SortResult;

Initialization and memory management.

  const T = usize; // node data type
  var tsort = try TopoSort(T).init(allocator, .{});
  defer tsort.deinit();

节点值的数据类型作为编译时类型提供给 TopoSort(T)。

Adding dependency data.

  try tsort.add(101, 102);  // node 102 depends on the leading node 101
  try tsort.add(102, 103);
  try tsort.add(101, 104);

Performing the topological sort

  const result = try tsort.sort();

Checking for cycles

  if (result.has_cycle()) {
    for (result.get_cycle_set().items) |id| {
      const cyclic_node = result.get_node(id);
      ...
    }
  }

Otherwise, process the sorted non-cyclic result

  const sets: ArrayList(ArrayList(T)) = result.get_sorted_sets();
  for (sets.items) |subset| {   // the node sets are in topological order
    for (subset.items) |node| { // nodes within each set are dependence free from each other.
      ...
    }
  }

TopoSort 计算出在拓扑序列的线性顺序中彼此没有依赖关系的节点，并将它们组合成子集。 这允许你并行运行/处理每个子集的节点。

子集本身按拓扑顺序排列。 如果不需要并行处理，则可以按顺序处理每个子集中的节点，这符合所有节点的整体拓扑顺序。

Memory Ownership

节点通过 add() 中的值传入，并按值存储在 TopoSort 的 Data 结构中。 对于像 integer 这样的简单类型（例如 u16、u32），节点值只是被复制。 对于 slice 和指针节点类型（例如 []const u8），不会复制节点的内存。 内存由调用者拥有和管理。

Configuration

Toposort.init() 函数接受可选配置。 例如

  const T = usize; // node data type
  var tsort = try TopoSort(T).init(allocator, .{
    verbose = true,
    max_range = 4000,
  });

设置 verbose 标志会在排序时打印内部消息。

max_range 属性设置节点项目值的最大值。 例如，对于范围为 1、2、3、20、75、... 100 的节点值，100 是最大值。 如果你的所有节点值都是正整数，则传入数字类型（u16、u32、u64 等）作为节点数据类型并设置 max_range，则 TopoSort 可以使用更简单的数据结构，从而获得更快的性能。 构建依赖树的速度可能提高 3 倍或 4 倍以上。 比较 tests.zig 中的第 3 个基准测试和第 4 个基准测试。

More Usage

To use a slice/string for the node type,

  const T = []const u8;
  var tsort = try TopoSort(T).init(allocator, .{});

To get a list of topologically sorted nodes.

  const T = []const u8;
  var list = ArrayList(T).init(allocator);  // list to hold the returned nodes.
  defer list.deinit();
  for ((try result.get_sorted_list(&list)).items) |node| {
    ...
  }

To add dependency similar to the Makefile rule format.

将依赖节点 A 添加到前导 B 节点。 A: B 将依赖节点 B 添加到前导 C 节点。 B: C 将依赖节点 B 添加到前导节点列表。 B: E F G

  const T = []const u8;
  var tsort = try TopoSort(T).init(allocator, .{});
  try tsort.add_dep("A", "B");  // A: B
  try tsort.add_dep("B", "C");  // B: C
  try tsort.add_dep("B", "D");  // B: D
  try tsort.add_deps("B", &[_]T{ "E", "F", "G" });  // B: E F G
  
  var nodes = ArrayList(T).init(allocator);
  try nodes.append("E");
  try nodes.append("F");
  try nodes.append("G");
  try tsort.add_deps("B", nodes.items);

To traverse the list of nodes in the graph,

  for (result.get_nodes().items) |node| {
    ...
  }

To traverse the dependency graph recursively,

  const T = usize; // node data type
  var tsort = try TopoSort(T).init(allocator, .{});
  ...
  const result = try tsort.sort();
  visit_tree(result, null, result.get_root_set());
  fn visit_tree(result: SortResult(T), lead_id: ?u32, dependent_ids: ArrayList(u32)) {
    if (lead_id) |id| { // lead_id is optional since the root nodes have no leading nodes.
      const lead_node = result.get_node(lead_id);
      ...
    }
    for (dependent_ids.items) |node_id| {
      const dependent_node = result.get_node(node_id);
      ...
      visit_tree(result, node_id, result.get_dependents(node_id));
    }
  }

Command Line Tool

TopoSort 附带一个命令行界面 (CLI) 工具 toposort-cli，它在内部使用 TopoSort 库。 它使用的数据文件遵循 Makefile 的简单依赖规则格式。 例如

 A: B
 B: C D
 C: E F G

测试数据的示例调用：

 zig-out/bin/toposort-cli --data data/data.txt
 zig-out/bin/toposort-cli --data data/data.txt --verbose
 zig-out/bin/toposort-cli --data data/data2.txt
 zig-out/bin/toposort-cli --data data/data_cycle1.txt
 zig-out/bin/toposort-cli --data data/data_cycle2.txt
 zig-out/bin/toposort-cli --data data/data_num.txt --int

Benchmarks

TopoSort 附带一些基准测试。

运行 zig build test -Doptimize=ReleaseFast 以运行基准测试。

License

TopoSort 采用 MIT 许可。

Further Reading

有关 Zig 构建系统的更多信息，请查看以下资源：

About

Topological sort library in Zig

Resources

Readme

License

View license

Activity

Stars

18 stars

Watchers

1 watching

Forks

1 fork

Report repository

Releases 3

Release 1.0.2 Latest Apr 1, 2025

+ 2 releases

Packages 0

No packages published

Languages

Footer

© 2025 GitHub, Inc.

Footer navigation