Bill Brasky Bill Brasky - 1 month ago 23
Java Question

Directed Graph Processing in Java

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:


  1. Define the graph of tasks

  2. Ensure there are no cyclic dependencies in the graph

  3. 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.

Answer

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.