0

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

vkp
  • 91
  • 4
  • 17
  • Since JOB3 depends on nothing, there is something wrong with your input to the 'topological iterator' since it is showing JOB3 depending on job1. You need to post your input. – ravenspoint Jul 12 '23 at 15:32
  • @ravenspoint apologies for the confusion, have added sample code and o/p – vkp Jul 12 '23 at 17:39
  • Question seems to be a duplicate of: [Topological sort with detecting vertices that have equal priorities with JGraphT](https://stackoverflow.com/questions/69745237/topological-sort-with-detecting-vertices-that-have-equal-priorities-with-jgrapht/69758522#69758522) Also related: [Using JGraphT to Manage Ordering of Dependent Tasks](https://stackoverflow.com/questions/46840485/using-jgrapht-to-manage-ordering-of-dependent-tasks) – Joris Kinable Jul 12 '23 at 17:58
  • @JorisKinable yes, that answers it. Thank you so much. – vkp Jul 12 '23 at 18:05

0 Answers0