Queue reduction algorithm?

Question

I have a queue of activities shared between clients, capturing user activity and executed by a robot on the other site. An example of activites might be like:

CREATE FOLDER  /docs
CREATE FILE    /docs/journal.txt
DELETE FILE    /docs/blog.txt
MOVE   FOLDER  /docs/images /docs/photos
...

Often there are activites that can be reduced to a single one, or none. For instance:

CREATE FOLDER /docs
RENAME FOLDER /docs /documents

Can be simply changed to:

CREATE FOLDER /documents

And something like:

CREATE FOLDER /docs
RENAME FOLDER /documents
DELETE FOLDER /documents

Can be removed entirely from the queue.

This kind of reduction/optimization seems like a very generic problem, and before attacking it I'd like to try some generic solution. It looks like a pathfinding optimization problem.

Any ideas?

Answer 1

One option (albeit a somewhat heavyweight one) would be to walk over the queue records and simulate the operations that are performed on the file system on a tree representation that you create inside the program. You could track, for each directory that's referenced, what net operations end up being performed on it. Once you're done, you could then walk over the modified tree structure and output a series of commands representing the net transformation applied to each directory and subdirectory.

Hope this helps!

Answer 2

I don't know of any library or framework that would do this for you. On the other hand, you would have to specify the logic behind it yourself, and as I see it, that would be the bulk of the work anyway.

Here's the approach I would take:

1. Do a topological sort of the actions (rename folder "depends on" create folder and so on...)

2. Each command with no dependencies represents a "root" in a dependency tree.

3. Collapse these trees recursively starting from each root.