Ordering 'Tasks' for execution based on their dependencies

Question

Let's say I have a set of Tasks that they have dependencies. These tasks are not in order, but the execution of tasks should be in the proper order. Each task has two properties: Before and After.

Before contains list of tasks that are dependending to the result of this task -- so it should be run before them; After contains list of tasks that this specific tasks depends on them. So there are two ways to say B depends on the result of A:

a) Add A to the B's After list

b) Add B to the A's Befor list

Either way should work. Also there can be gap between tasks and it should be filled-up automatically on the execution time. For example imagine we have the following tasks:

Task1
  |____ Before: Task3, Task4
  |____ After: NA

Task4
  |____ Before: Task8
  |____ After: Task3

Task2
  |____ Before: NA
  |____ After: Task1

Task3
  |____ Before: Task5
  |____ After: Task2

Task5
  |____ Before: Task7
  |____ After: Task3

So here there is a little bit ambiguity about which task should run first: Task4 or Task5? But it is not important as long as they get executed after Task3 and before Task7 and Task8. This is up to the algorithm to put them in the right place.

The only way that I can think of doing this is to scan all of the tasks first and basically register the dependencies and then start over and execute each task now in their proper order.

The complexity/efficiency of the algorithm is not very important as I have less than 500 Tasks to order before executing them, but I prefer to use a well-known algorithm or method to solve this, rather putting things together just to get it done.

Update: The main reason I need both Before and After properties is to reduce human error while creating tasks. e.g. It is more semantic to say CreateDirectory is After LoadConfiguration and Before CopyFiles. Of course you can say CopyFiles is after CreateDirectory, and CreateDirectory is after LoadConfiguration.

But in the end all of these will be converted only to After properties.

Answer 1

You have a Directed Acyclic Graph and you need to operate a Topological Sorting to order your graph.

The details of implementation depends to the programming language and platform you are working on so it's up to you to find a graph library and so on to use in your application.

Alternatively Tsort can be helpful also.

Answer 2

Beyond @53777A's fine answer, your before & after information is "interesting". You don't need both before and after information, so I wonder why you bother to capture both.

When we do have both before and after information, in a canonical form, the information would appear symmetric, which is to say that if Task1 should be before Task3 then Task3 should be after Task1, and so on, which isn't the case in your data sample.

You can easily get such a before & after canonical form from either what you have or from an after-only or before-only dependency list, by a simple traversal where you ensure the symmetric reverse link is present.

However, using just after information (though made canonical if starting from your non-canonical before and after capture), you can simply run any task that is ready (all its after's have already run). You just need to be able to tell which ones have run so far.

By the way, that is exactly a topological sort, it's just that you're doing it on the fly instead of in advance. If you number them as you visit them instead of executing them, then you've create the sorting order, and if you put them in a list as you visit them, you've created an topologically ordered list.

I'm sure that there are more efficient ways to identify what may be runnable next at any point, which would be useful for larger extreme data sets, but in a simplest case, you can just scan the list for any item not yet run/visited whose after's have all run/visited. You can use two lists instead of or in addition to boolean state for ran/visited.

If you find that there are still elements left that aren't visited, and you cannot identify one to run next, then you have a cycle, which represents an error in the input. That's not unlikely if humans are maintaining the before & after information for these 500 tasks, so doing the sort can be used to find these error before you do the execution run.