The Algorithm Behind the Topological Sort Library TopoSort

7 points by ww520 21 hours ago

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.