I've read a section about Ershov numbers in the Dragon Book and one of exercises for the section tells me to make rules of calculation of the numbers for a DAG case.

For how it is explained in the book, DAG is a "tree" where a node can have got more than one parent. The content of the section explains how to do Ershov numbers for a classical tree.

My train of thought is that when we find a node with many parents, there is a sub-graph with nodes between the node and a node that joins two "branches". Thus, in one branch we have to keep a register assigned to the split-node, making this branch with one extra register busy, and the other branch where we consume the value in that register, making this branch with one less register to use.

The problem with my approach is that the way to choose which of the branches is the "keeper" and which is the "consumer" is non-deterministic. For me, they can be chosen at random, but the way how I select it makes the rest of the DAG change their numbers to, which may result in very different numbers assigned to nodes.

Is there any other way to solve the exercise?