[Recipe] Topological sort

[lassik]

Problem

Given a directed acyclic graph (DAG) describing how nodes depend on other nodes, visit the nodes in an order where all dependencies of each node are visited before that node. This algorithm is known as topological sort.

For example, the Unix make program does a topological sort to figure out the build order for the files.

Solution

Public domain, from Shiro Kawai: https://github.com/shirok/Gauche/blob/master/lib/util/toposort.scm

[lassik]

https://en.wikipedia.org/wiki/Topological_sorting

[lassik]

Now at https://cookbook.scheme.org/topological-sort/