Circular Dependency Problem

I was thinking this morning(morning, from my POV) how to solve the problem of having several analytics running, some of which depend on others.

For instance, suppose I have 2 programs: A and preA; and A depends on preA.

That would require me to try to run A, and if failing due to unsatisfied dependencies, put it in a wait-list and running preA first. Then going back to A.

Now, what about postAB,A,B,preA,preB?

I guess a possible(but inefficient) solution would be to try running all of them, putting the ones that do not run in a wait-list, then iterating the wait-list again and again until all of them had ran or had no hope of having their dependencies satisfied.

Like this:

postAB(depends on A and B, wait-list)
A(depends on preA, preA didn’t run yet so put A in wait-list)
B(depends on preB, wait-list)preA(runs)

2nd iteration:

postAB(wait-list again)




Now, this lead to quite some processing time. N+(N-1)+(N-2)..(N-(N-1)) attempts in a worst case scenario.

One way of mitigating this might be to sort the initial list in a way that programs with fewer dependencies go first:

In this case we would go from 3 iterations in the initial case to just 1. 🙂
The worst case scenario would remain the same though.


Leave a comment

Filed under Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s