How to interpret the BDD2ZDD algorithm

Question

Variable ordering : p3 > p2 > p1 > p0

I have above ROBDD, how could I implement the BDD2ZDD algorithm like what should be the starting node i.e b here, and as I understand from lecture that 'j' should be the next highest variable in variable ordering then in this case ?

Could you please explain the 'b' and 'j' ? 

Also the last else conditions explicitly says D(label(b)) < j, but there is no condition for D(label(b)) > j so else will be applied in that case as well. Please explain.

Answer 1

If you have variables p0<p1<p2<p3, then the degree of these variables is 2<3<4<5. The function BDD2ZDD should be initially called with the highest degree, i.e., j=5, and the root node b of the given BDD.

We then either have D(label(b))=j which would mean that the root node of b is labeled with variable p3 that has degree j=5, or we have D(label(b))<j which would mean that the root node of b is labeled with variable less than p3, i.e., one of p0,p1 or p2. 

The case D(label(b))>j that you are missing cannot exist, since that would mean that the BDD contains a variable whose degree is greater than the highest one that we expect. That would be a bug!