0
$\begingroup$

DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?

Is there an algorithm for generating topological sequence from DAG with such constraint? Or maybe I can transform the DAG with this constraint?

$\endgroup$
2
  • 1
    $\begingroup$ If $x$ cannot appear before $y$, then it must appear after $y$. $\endgroup$ – Yuval Filmus Oct 9 '20 at 15:28
  • $\begingroup$ (… as they cannot appear in the same position of a linear sequence.) $\endgroup$ – greybeard Oct 10 '20 at 7:38
0
$\begingroup$

Let's say the 2 nodes in question are node x and node y. If you want node x to not appear before node y, then, as Yuval Filmus mentioned in the comments, you want it to appear after y.

What does this mean?

If x is a predecessor of y, then the graph would not be valid, because by definition, a topological sort puts all predecessors before their childrens.

If x is not a predecessor of y, you could add an auxiliary edge from x to y. This ensures that x will definitely appear before y, again by definition of a topological sort.

Followup:

Adding an auxiliary edge may cause some problems, here are some possible solutions to resolve them

Shortest/longest path in weighted DAG: Just set the edge weight as 0

Shortest/longest path(number of edges used): Give all non-auxiliary edges value of 0, treat as SP/LP in weighted DAG

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.