Show HN: The Algorithm Behind the Topological Sort Library TopoSort

Summary

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. 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. 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} By definition, a topological order of the nodes of a directed acyclic graph (DAG) is that the nodes are linearly ordered in such a way that a node has no dependence on any other nodes coming after it. In a DAG graph, there exist some nodes which depend on no other nodes. These are the root nodes of the graph, where graph traversal begins from them. These form the inital root set. We define that when a node y depends on x, node y has an incoming link from x. When node x is removed, the incoming link to y is removed as well. Removing the nodes of a root set from the graph causes the remaining nodes depending on them to have one less dependence, i.e. their incoming links decremented. For the nodes whose incoming links reaching 0, they become the new root nodes since they depend on no one. We define that set A has no dependence on set B when all members of A have no dependence on any member of B. It follows that each root set removed during the iteration has no dependence on any other root sets coming after it, thus the sequence of successively removed root ...