2

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.

vasanth
  • 130
  • 1
  • 2
  • 11

2 Answers2

3

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.

Artium
  • 5,147
  • 8
  • 39
  • 60
  • If you have a cycle, you have a plugin A that depends on a plugin B that depends A. Topological sort not working would be the least of your problems. – toto2 Jun 25 '11 at 12:35
  • @toto yes, but as @artium mentioned CycleDetector would take care of that, am in the process of trying out his suggestion, will post my progress soon – vasanth Jun 25 '11 at 18:15
  • Thanks @Artium `TopologicalOrderIterator` along with a `CycleDetector` did what is required. – vasanth Jun 30 '11 at 05:45
  • I am trying to use JGraphT's TopologicalOrderIterator to get a scheduling order. The iterator returns one node at a time. But in a topo sort, there might be more candidates in each iterations. Is it possible to get all the candidates so that I can do a parallel execution on them? – amrk7 May 31 '16 at 02:14
  • @amrk7 Don't familiat enpugh with JGraph, but you can mae minor alternation of Kahn's algorithm (https://en.wikipedia.org/wiki/Topological_sorting) – Artium Jun 02 '16 at 21:39
0

I would suggest a simple load-on-demand approach, load all plugins a plugin depends on if not already loaded.

A few observations:

  1. If the dependency tree is very deep (> 1,000 plugins), this could result in a StackOverflowException
  2. This solution is thread-safe assuming all plugins are loaded one by one and synchronously
  3. Finding illegal cycles in the "graph" is handled by using a starting flag that is set to true before loading all dependencies and set back to false only after the plugin is initialized
  4. This case handles the situation when a plugin explicitly starts another plugin (not as part of its dependencies -- but it does not account for asynchronous initialization)

Here is an untested sample to give an idea:

class Plugin {
    Set<Plugin> dependencies;
    boolean started, starting;

    Plugin(Set<Plugin> deps) { dependencies = deps; }

    void start() {
        if (started) { /* already initialized */ }
        else if (starting) { throw new IllegalArgumentException("Cyclic plugin dependency"); }
        else {
            starting = true;
            for (Plugin p : dependencies) { p.start(); }
            /* initialize this plugin here */
            starting = false;
            started = true;
        }
    }
}
Nick
  • 5,765
  • 5
  • 27
  • 36
  • the plugins are not runtime dependent on each other, the application is more like a build tool, where i execute the plugins in particular sequence, in any case i wouldnt want the plugins to be hold references (set deps), i am looking for a solution where u simply mention a particular plugins id as dependency, thus the main program based on the information would decide the execution order. Thanks. – vasanth Jun 25 '11 at 12:07
  • You can still use this approach by using `int` instead of `Plugin` and basically extracting the right order of the IDs -- but doing topological sorting is your better bet. – Nick Jun 25 '11 at 19:42
  • trying to extract the right sequence of id would force the plugin writer to decide the sequence ... it can be implemented using Comparable interface, i want the program to 'resolve' the order ... i will be tryin to use the Topological Sort ... thanks – vasanth Jun 26 '11 at 17:18