Show HN: The Algorithm Behind the Topological Sort Library TopoSort

TopoSort Algorithm William Wong, 2025-04-02 The algorithm used in TopoSort is a variant to the Kahn's algorithm in working on the nodes as sets instead of as individual nodes, with the additions on finding dependence-free subsets and finding cyclic nodes. Overview The main idea is to iteratively find the successive root sets of the graph after removing them at each round. Here's a high level outline of the algorithm. Find the first root set of the graph. Remove the nodes of the root set from the graph. Find the next root set. Go to 2 until the graph is empty. The successively removed root sets form a topological order. The nodes within each root set are dependence free in the root set. Further the nodes are a topological order when lined up in the order of the root sets. Example For a graph with nodes {a, b, c, d, e, f} , successively removed root sets look like: {a, b} | {c, d, e, f} {a, b} {d} | {c, e, f} {a, b} {d} {c, e} | {f} {a, b} {d} {c, e} {f} Rational By definition ... Read full article.