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.