How to do a reverse topological sort using depth first search?

Question

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?

Answer 1

I'm not sure about the algorithm modification to directly call the callback function in a reverse order, but I found a way to do this without extra memory allocation.

My solution is to embed a doubly linked list node within the data structure storing rules. (It actually turns out there was already a linked list node in the data structure I used for other purposes, and I have the ability to reuse this existing linked list node because the two linked lists are disjoint!)

In some cases, linked lists require extra memory allocation, namely if you want to have the ability to store an object into more than 1 linked list at the same time. However, if you only need to ability to store the object into 1 linked list, you can embed the linked list node within the object itself.

Then, the embedded linked list nodes are used to construct a linked list of all files/directories that need removal using the standard topological sort based on depth first search. When a depth first search finds a file/directory to be removed, it is added to the linked list.

It is trivial to iterate a doubly linked list in whatever order: either the insertion order or the reverse of it.

Arguably, a singly linked list would work too, but I already had a doubly linked list node embedded within the data structure, so the "optimization" to use a singly linked list would not be an optimization in my case at all.

Answer 2

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.