Resolve dependencies using before-after constraints

Question

What i would like to do is the following.
(Not sure if this question should go to StackOverflow, or here)

Consider a datastructure like this:

interface IAction {
    IAction[] afterActions()
    IAction[] beforeActions()
    void execute()
}

What I would like to do is execute() a IAction collection, in the manner, that

1. All beforeActions() are executed before the supplier of the beforeActions() calls result.
2. All afterActions() are executed after the supplier of the afterActions() calls result.
3. Be able to detect "cyclic dependencies", so if one should execute before and after another, or after itself, or after another action, that on any path should execute before, etc.

In other worlds I would like to "sort" these actions in an executable order.

I would like to get only an explanation on how I should (could) do this, I don't expect anyone to implement anything for me (notice, that I intentionally didn't specify a language).

If you know about any generic algorithm for this purpose, that you think is suitable for the problem, please feel free to share with a minimal explanation, on how you would translate it to this problem

---

EDIT

After thinking a lot about the problem, I figured out, that dependency-wise the afterActions() is absolutely useless (an action shouldn't know about what executes after it, it should only describe what it needs to be completed before, to successfully execute). Knowing this I ended up doing something like what @Rafael Eyng suggested:

I created an Iterator, which wrapped the original collection, and had a next(), which always returned the next (resolved) action. The iterator was not stateless, it had a reference to the collection with all the action, and had a (growing) Set of actions, which are resolved. To achieve this, every time next() was called i did the following:

1. Iterate on all the actions
2. If one has no dependencies, or all of them are in the already resolved list, then it can be returned as next.
3. If it has dependencies, then recursively do this for all the prerequisites.
4. I was also collecting the already visited actions, from the root of the recursive call, so cycles could be detected

Answer 1

First of all, you should have a (let's call it) ready collection of IAction's whose dependencies were already met. This collection starts empty, of course. Then you should iterate over your IAction instances and check whether all of its dependencies were met. You do this by iterating over all the dependencies and checking whether all of them are present in the ready collection. If all dependencies of some IAction instance are present in the ready collection, you can put this IAction instance in the ready collection as well. Now on, you don't check this IAction dependencies anymore, by removing it of your unresolved IAction's collections or flagging it as ready to run.

Of course this assumes that there will be some IAction's that doesn't have any dependencies (that will be the first ones to be inserted in the ready collection), or more broadly, there are no ciclic dependencies. But I think it might give you a good first implementation to work on top of.

Answer 2

For question 3, you will need to recursively iterate over the graph of IAction instances entirely. Recursive iteration is a basic operation. If you don't know how to do that, read up on recursive tree traversal. You can detect cyclic dependencies in at least two ways:

• Use a class instead of an interface, and use a boolean field in the class to indicate that instance has been visited already. If during the iteration, you visit the same instance twice, you have detected a cycle.
• Use a collection of IAction instances, and add each instance to the collection when you visit it. You can detect cycles by noticing that an instance is already present in the collection, before you add it.