5
$\begingroup$

I'm given a finite partial order, in the form of a dependency graph between items, and I'd like to have it in series-parallel form (Wikipedia).

So formally, given a finite partial order $\le$ on a set $V$, I'd like to construct it using only the following rules:

  • For every item $P$ in $V$, we have the partial order on $\{P\}$.
  • Series. If we have orders $X$ and $Y$, then we also have $X;Y$, which adds both orders such that additionally for any $x,y \in X,Y$ we have $x \le y$.
  • Parallel. If we have orders $X$ and $Y$, then we also have $X + Y$, which adds both orders such that any $x,y \in X,Y$ are incomparable ($x \not\le y \land y \not\le x$).

What kind of algorithm could I use to construct this SP-form?

(I'm aware that the graph is required to be "N-free" for an SP-form to exist.)

For a larger graph which is regularly updated, it would be helpful if the algorithm were incremental, but I have no idea whether that would be possible.

Examples. Writing $P$ for the partial order on the single-element set $\{P\}$, a linear order would look like $A;B;C;...$ (all in sequence). The "unorder", where different items are incomparable, would look like $A+B+C+...$ (all in parallel). A binary tree could look like $A;((B;(C+D))+(E;(F+G)))$.

Background. In a task list or issue tracking application which allows you to specify dependencies between tasks or issues, it seems helpful to present them in a series-parallel form, instead of the usual flat list which at most is topologically sorted.

$\endgroup$

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.