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)
preB(runs)

2nd iteration:

postAB(wait-list again)
A(runs)
B(runs)

3rd:

postAB(runs)

———————————-

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:
preB,preA,A,B,postAB

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.

Advertisements

Leave a comment

Filed under Uncategorized

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s