Parse DAG into task tree Suppose we have a DAG of tasks:



Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, 9) must be run sequentially (Seq block).

I need to parse this DAG into recursive structure of Seq and Par blocks (collections). DAG from the image above may be represented by the following structure:

Seq(
    1,
    2,
    Par(
        Seq(7, 8, 9),
        Seq(
            3,
            Par(4, 5, 6),
            10
        )
    )
)


Each DAG may be represented by a set of Seq-Par structures. I want to search for the most optimal. Optimality criteria — run in parallel as much as possible (without breaking dependencies).

More on optimality criteria: all tasks' have the same execution time T. Execution time of Seq(1, 2 ... N) equals to N * T. Par(1, 2 ... N) = T.

I believe, that this task is pretty well-known and simple. Can you, please, name some algorithm solving this problem.

If we add edge from 7 to 4 (proposal from comments), then one of representations may be:

Seq(
    1,
    2,
    Par(
        7,
        3
    ),
    Par(
        Seq(8, 9),
        Seq(
            Par(4, 5, 6),
            10
        )
    )
)
Your problem is equivalent to scheduling unit-time tasks on infintely many machines with precedence constraints (which are by necessity DAGs) minimizing the maximum completion time. In scheduling literature, this is called project scheduling and also denoted as $P_{\infty} \mid \text{prec} \mid C_{\max}$.

This problem is known to be amenable to the critical path method (CPM) which creates an optimal schedule in time $O(n^2)$, $n$ the number of tasks.

Given a schedule $s : \mathbb{N}^2 \to T$ that maps pairs of time slot and  machine indices to tasks, you can derive a tree consistent with the precedence DAG of the form

$\qquad\displaystyle \mathrm{Seq}\bigl( \mathrm{Par}(s(1,1), \dots, s(1,i_{1})),\ \dots,\ \mathrm{Par}(s(t,1), \dots, s(t,i_{t}))\bigr)$;

here, $t$ is the time of the last scheduled task, and $i_j$ is the maximum index of busy machines at time $j$. (I assume that at any given time $j$, machines $1, \dots, i_j$ are busy and $i_j+1, \dots$ idle.)

If that schedule is optimal, the tree is, too. It does not hold information about the original DAG, though.