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.


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.