Java code to convert a list of dependencies into a build order?

Question

Given I have a list of dependencies available as bits in external files. These will be aggregated into a list like:

module1
module2 dependsOn module1
module3 dependsOn module1
module4 dependsOn module3

I would like to create a build order where each build step is found on one line, and each line contains a list of one or more modules which can be compiled at the same time, and which only depend on modules compiled earlier.

So, for the above data set, create a list like:

module1
module2,module3
module4

Now, this is basically just a problem of creating a directed graph, and analyzing it. Now, I am using Ant, and would very much like to use something off-the-shelf... what is the minimum of custom code I need to have it create such a dependency-aware build list starting from the given input? I do not want to write all code myself (which I know how to do), but looking for libraries to help me here...

BTW, these modules are actually custom modules, so maven will not work. Moreover, the module list is created on the fly from the Java source code, and I cannot hard code this in the build file.

Answer 1

Draw a tree of your dependencies and look at the levels. You can start building at the root and build each level of the tree in parallel given that the levels above are already built.

1----->2
 |
 ----->3----->4

^      ^      ^
|      |      | 
A      B      C

Build A first (module 1), then B (2&3), then C (4).

EDIT: If you are using Ant and are asking specifically for a dependency resolution solution for Ant, you could take a look at Apache Ivy

Answer 2

Ant can handle that for you. You basically describe your module dependencies as target dependencies. Have a look at [http://stroy.wikidot.com/motpe]. It is 2 ant scripts with same conventions to handles multi module builds.

Answer 3

You can use topological sorting to see how the real ordering is. This can be done by using unix util tsort or you can search for an implementation for toplogical sort (Excalibur Framework has something like this).