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 next, useful for larger 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 run/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 run.

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.

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 next, useful for larger data sets, but in a simplest case, you can just scan the list for any item not yet run whose after's have all run.

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 next, useful for larger 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 run/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 run.