Queue reduction algorithm?
algorithm, optimization, queue
Solution
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:
Do a topological sort of the actions (rename folder "depends on" create folder and so on...)
Each command with no dependencies represents a "root" in a dependency tree.
Collapse these trees recursively starting from each root.
Problem
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?