I have a directed acyclic graph where the nodes are tasks and the edges are dependency relations between tasks - the edges go from the dependency to the task that depends on it. It is possible that multiple tasks depend on the same parent task and that a task depends on multiple other tasks, so it can be any DAG.
I need to transform this DAG to satisfy the following constraint:
Forks (nodes that have multiple children) and joins (nodes that have multiple parents) must come in pairs - all paths coming from a fork must eventually converge to the same join.
To me it seems that there are DAGs that cannot be transformed without adding new dependencies, which may reduce the parallelism (and thereby execution speed). I'm looking for an algorithm that transforms the DAG in a way that:
- No dependencies are deleted - this is an absolute requirement, since a task cannot run until all of its dependencies have completed. This means that if there is a path from node A to node B in the original DAG (respecting the direction of the edges), there must be a path in the transformed DAG, too.
- New dependencies are only added when necessary - if the original DAG can be transformed to fork-join format without adding dependencies, we should not add any.
- If it is necessary to add new dependencies, we should add as few as possible.
Of course 3. is not an absolute requirement (nor is 2., but I'd like to have that one if possible).
Thanks in advance,
Daniel