Directed Graph Processing in Java

Question

I am looking to implement a Java application that will compute a set of tasks to execute. The tasks will have dependencies on each other, forming a directed graph. Is there an existing SDK or algorithm (preferably in Java) out there that will help me:

Define the graph of tasks
Ensure there are no cyclic dependencies in the graph
Execute the tasks in the graph using a thread pool

Step 3 is the most important part. I need to execute the tasks in a parallel fashion for maximum performance yet ensure that a task isn't executed before its dependencies.

score 4 · Accepted Answer · edited May 23 '17 at 12:09

4

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.

edited May 23 '17 at 12:09

Community

1
1

answered Jul 19 '11 at 15:11

brain

5,496
1
26
29

Thanks. Saved me a bunch of time on the graph part and the rest wasn't too hard after that to just submit unreferenced vertexes to a ThreadPoolExecutor. – Bill Brasky Jul 19 '11 at 21:49

score 3 · Answer 2 · edited Feb 27 '20 at 10:58

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

Disclaimer : I am the owner

score 2 · Answer 3 · answered Dec 29 '11 at 22:02

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.

first link is dead, but the git-repo is alive and well (last commit 11 years ago though...) — julaine, Dec 01 '22 at 15:11

score 0 · Answer 4 · answered Aug 12 '11 at 20:37

0

I've use JUNG for creating dependency-graphs among files. There are a variety of classes for computing distances, clustering, etc.

answered Aug 12 '11 at 20:37

Darien

3,482
19
35

Directed Graph Processing in Java

4 Answers4

Linked

Related