The Algorithm Behind the Topological Sort Library TopoSort

  • Posted 6 days ago by ww520
  • 7 points
https://github.com/williamw520/toposort/blob/master/Algorithm.md
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.

2 comments

    Loading..
    Loading..