Directed Graph Processing in Java

Dexecutor to the rescue, Dexecutor is designed to execute dependent independent tasks in a reliable way. 

DexecutorConfig<Integer, Integer> config = new DexecutorConfig<>(executorService, new SleepyTaskProvider());
DefaultDexecutor<Integer, Integer> executor = new DefaultDexecutor<Integer, Integer>(config);
// Graph building
executor.addDependency(1, 2);
executor.addDependency(1, 2);
executor.addDependency(1, 3);
executor.addDependency(3, 4);
executor.addDependency(3, 5);
executor.addDependency(3, 6);
executor.addDependency(2, 7);
executor.addDependency(2, 9);
executor.addDependency(2, 8);
executor.addDependency(9, 10);
executor.addDependency(12, 13);
executor.addDependency(13, 4);
executor.addDependency(13, 14);
executor.addIndependent(11);
//Execution
executor.execute(ExecutionConfig.NON_TERMINATING);

Refer How Do I? for more detail

Why Dexecutor

  • Ultra light weight
  • Ultra Fast
  • Immediate/Scheduled Retry Logic supported
  • Non terminating behaviour supported
  • Conditionally skip the task execution
  • Good test coverage to keep you safe from harm
  • Available in maven central
  • Good amount of documentation
  • Distribute Execution Supported (Ignite, Hazelcast, Infinispan)

Usefull links

  • Dexecutor Blogs
  • Dexecutor Website
  • Dexecutor Wiki
  • Dexecutor Source Code

Disclaimer : I am the owner


Have a look at this previous question, which essentially suggests using JGraphT.

It will obviously make 1) easy and has cycle detectors for part 3). Don't think it will do part 3 for you but all you need to do is get all vertexes with an out degree (or in degree depending on your representation) of 0 and start those tasks. When a task finishes then delete the vertex from the graph and start again.


I have created a Java library that does exactly what you are requesting. You can construct a directed graph consisting of Runnable objects and their dependencies. You then pass this graph to an executor that runs the objects as their dependencies are fulfilled, in an executor.

Download the library's jar file here: https://github.com/idooley/DAGExecutor/downloads

Or clone the whole repository and compile it yourself: https://github.com/idooley/DAGExecutor

Hopefully this will be of use to others. Feel free to contribute any patches, new unit tests, or other changes to make it work the way you want for your projects.

Tags:

Algorithm

Java

Multithreading

Graph

Threadpool

Recent Posts