How to do a reverse topological sort using depth first search? I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files and directories are targets, and then deletes those, if the user wishes to do a clean operation. However, a file may reside in an automatically created directory, meaning I should do a topological sort for the targets, where every file has an arc towards the parent directory, and every directory has an arc towards its parent. So, for example:


objhierarchy/obj/foo.o has an arc towards objhierarchy/obj
objhierarchy/obj has an arc towards objhierarchy


What complicates the things is that the files need to be deleted in the reverse order. So, in the example given, you need this order: (1) objhierarchy/obj/foo.o, (2) objhierarchy/obj, (3) objhierarchy.

Topological sort seems like a good solution, but it gives the opposite order. So, a topological sort of the directory parent graph would yield (1) objhierarchy, (2) objhierarchy/obj, (3) objhierarchy/obj/foo.o.

A solution could be a buffer of pointers that is reversed in-place (or just iterated in the reverse order), but I would like to avoid allocating extra memory.

What is the best way to get the files deleted in the reverse order? Can the topological sort algorithm based on depth first search be modified to call some callback function in a reverse order?
In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree.

Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the files to be deleted in order (starting from the top of the stack). Due to the nature of DFS/BFS on trees, every node will be pushed to and popped from $S$ before its children. Therefore, every time we pop a node from $S$, we add it to the stack $T$. At the end of the search $T$ will maintain the property that all nodes appear deeper in the stack than their children. Keep in mind this only works if the file node structure is a tree not a DAG.