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.

回答1:

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.

回答2:

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

回答3:

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.

回答4:

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