←back to thread

Show HN: Zig Topological Sort Library for Parallel Processing

(github.com)
114 points ww520 | 1 comments | 01 Apr 25 17:48 UTC | HN request time: 0.21s | source

I believe the best way to learn a language is by doing an in-depth project. This is my first Zig project intended for learning the ropes on publishing a Zig package. It turns out to be quite solid and performant. It might be a bit over-engineered.

This little library is packed with the following features:

  - Building dependency graph from dependency data.
  - Performing topological sort on the dependency graph.
  - Generating dependence-free subsets for parallel processing.
  - Cycle detection and cycle reporting.
1. emmanueloga_ ◴[02 Apr 25 01:43 UTC] No.43552977[source]▶
For those that have not implemented toposort or don't remember it: 1) only directed graphs without cycles can be topologically sorted (DAGs) 2) there can be more than one topological order and 2) reverse post order of depth first traversal from every unvisited node shields a topological order.

In JavaScript:

    function toposort(graph = { a: ['b', 'c'], b: ['d'] }) {
      const order = [];
      const visited = new Map();
      
      function dfs(node) {
        const status = visited.get(node);

        if (status === 1) throw new Error("Cycle found.");
        if (status === 2) return;

        visited.set(node, 1); // In progress.
        const adjacent = graph[node] ?? [];
        for (const neighbor of adjacent) dfs(neighbor);
        visited.set(node, 2); // Done.

        order.unshift(node); // Reverse post order.
      }

      for (const node in graph) {
        if (!visited.has(node)) dfs(node);
      }

      return order;
    }