2
$\begingroup$

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:

  1. 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.
  2. 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.
  3. 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

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Perhaps you could define your problem more formally? Examples would also be helpful. $\endgroup$ – Yuval Filmus Jul 28 '17 at 12:19
  • $\begingroup$ More specifically it would be interesting to have the exact definition of what is a DAG in fork-join format. $\endgroup$ – md5 Jul 28 '17 at 13:46
  • $\begingroup$ Also, how do you want to measure the number of new dependencies? By the number of edges in $G'$ that aren't in $G$? By the number of edges in the transitive closure of $G'$ that aren't in the transitive closure of $G$? (Where $G$ is the original graph and $G'$ is the transformed version.) Finally, are we allowed to add new vertices, or only new edges? And welcome to CS.SE! $\endgroup$ – D.W.♦ Jul 28 '17 at 16:41
  • $\begingroup$ I'm guessing the formal definition of fork-join format goes something like this: we say that vertices $v,w$ are a fork-join pair if $v \ne w$ and all paths that start at $v$ and end at a sink node go through $w$; and we say that $G$ is in fork-join format if for every vertex $v$ there exists a vertex $w$ such that $v,w$ are a fork-join pair. Is that what you had in mind? $\endgroup$ – D.W.♦ Jul 28 '17 at 16:44
  • $\begingroup$ @D.W. Yes, that's what I meant by fork-join format. I measure the number of new dependencies by the number of new edges in the transitive closures of the graphs. We are allowed to add new (dummy) vertices, not just edges. Thanks. $\endgroup$ – Daniel Jul 29 '17 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.