how to use Graph Theory for scheduling execution order?

Question

I am designing an application, which executes a series of plugins. A plugin's execution might/might not be dependent on another/other plugins execution. i.e some (not all) of the plugins expect other plugin(s) to be executed before it begins its execution.

I need to derive the correct order of execution such that no plugin gets executed before the plugin it's depending on.

I believe graph theory can be used to solve this (plugins as vertex, dependency as edge, and derive execution order using some sort of traversal).

I am planning to use JGraphT since the application is being developed in Java.

Any help or pointers to solve the case ??? i am not expecting whole java code, any pointers about graph theory (algorithms to use) will be equally helpfull ....

Thanks !!!

[solution:] @Artium lead to the solution, this link shows a very similar implementation.

Answer 1

I would suggest a topological sort.

And after a quick check, it is easy to do with JGraphT. Also notice:

For this iterator to work correctly the graph must be acyclic, and must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast; the results with cyclic input (including self-loops) or concurrent modifications are undefined. To precheck a graph for cycles, consider using CycleDetector or StrongConnectivityInspector.