Skip to content(if available)orjump to list(if available)

The Algorithm Behind the Topological Sort Library TopoSort

The Algorithm Behind the Topological Sort Library TopoSort

2 comments

·April 3, 2025

There are some interests on the algorithm behind the Topological Sort Library TopoSort posted a few days ago in finding the dependence free subsets for parallel processing. I've written down the explanation in the linked post.

In essence it is a variant of the Kahn's algorithm. It has sufficient differences that I feel it deserves a separate explanation. It approaches the problem with node sets in a graph instead of individual nodes. This makes the central idea very simple. See the algorithm outline in the write up.

Visit

pvg

Discussion the other day https://news.ycombinator.com/item?id=43549618

null

[deleted]