I’ve been tinkering with build systems lately, and the associated dependency graph between source artefacts. For anyone working on a system like this, you will eventually arrive at the algorithm for Topological Sorting. The Wikipedia page had a very good description of the algorithm, but I found another description that appeared clearer to me:

Repeat the following steps until the graph is empty:

Select a vertex that has no incoming edges.

Add the vertex to the sort.

Delete the vertex and all the edges emanating from it from the graph.

I thought it was a pretty elegant algorithm, and now that I know what I’m looking for, it turns up in a fairly large number of places.

reinventing make?

LikeLike

Yep 🙂

LikeLike