Graph - How to use topological sort to execute dependency tasks

Question

I have a usecase where I have jobs which can have dependencies or be boxes containing other jobs like in autosys.

For e.g JOB_BOX contains JOB1, JOB2 and JOB3 where JOB2 depends on JOB1 and JOB3 depends on nothing.

1. JOB_BOX
   • JOB1
   • JOB2
   • JOB3

boxes can contain box type job as well. so when someone triggers JOB_BOX the following should occur

1. Start JOB1 and JOB3 parallely
2. Once JOB1 completes start JOB2
3. Mark JOB_BOX complete when all of the jobs are complete.

I am using JgraphT DirectedAcyclicGraph to construct the graph of these jobs but I am not sure how to go about accomplishing this usecase using topological sort.

The topological iterator will give me [JOB1 -> JOB3 -> JOB2 -> JOB_BOX] but I will need to execute JOB1 and JOB3 simultaneously.

public class Main {
public static void main(String[] args) {
    DirectedAcyclicGraph<String, DefaultEdge> jobGraph = new DirectedAcyclicGraph<>(DefaultEdge.class);
    jobGraph.addVertex("JOB_BOX");
    jobGraph.addVertex("JOB1");
    jobGraph.addVertex("JOB2");
    jobGraph.addVertex("JOB3");
    //preReqJob -> Job
    jobGraph.addEdge("JOB1", "JOB_BOX");
    jobGraph.addEdge("JOB2", "JOB_BOX");
    jobGraph.addEdge("JOB3", "JOB_BOX");
    jobGraph.addEdge("JOB1", "JOB2");
    TopologicalOrderIterator<String, DefaultEdge> iterator = new TopologicalOrderIterator<>(jobGraph);
    iterator.forEachRemaining(job -> {
        System.out.print(job + " -> ");
    });
}

}

o/p for the above:

JOB1 -> JOB3 -> JOB2 -> JOB_BOX -> 

Idea is that I need to go in sequence of executing jobs based on the dependencies but also apply parallelism wherever applicable.

I have thought of an approach

Approach 1:

• I do the topological traversal and then for every jobName that I get I check the inDegree of that job i.e if(inDegreeOfJob == 0) then it is a candidate of simultaneous execution. that way I get JOB1 and JOB3 from the first set of traversal.
• Once JOB1 and JOB3 are complete, I check for subsequent jobs which are connecting JOB1 and JOB3 in that case I will get JOB2 alone since there is an edge from JOB1 -> JOB2
• once JOB2 is complete, I check for subsequent job which is connecting hence I get JOB_BOX and I mark that complete.

any help is appreciated and if there is any resource or any other approach you can point me to that would also be great.

Ref:

How to do Topological Sort (Dependency Resolution) with Java