CUDD package : Way to pass a specific variable order?

Question

I am working with the CUDD package to do BDD manipulations. I was wondering if anyone knows of a way to pass a specific variable order to instruct the program to use this order while building BDDs. I am working with Boolean functions that have a relatively small number of variables.

In fact, even if there is a way to pass to the program a particular input variable to root the BDD at, that would serve my purpose as well. If anyone knows how to do this, then I would really appreciate the help. I went through the documentation, and I did not find anything to this effect. Maybe I missed something.

Answer 1

You can set the reorder algorithm to CUDD_REORDER_NONE

Cudd_ReduceHeap(manager, CUDD_REORDER_NONE, 0);

In this way the order of the variables is given by the order you introduce them.

Answer 2

There are two functions in CUDD that do what the question asks:

• Cudd_AutodynDisable(manager): "Disables automatic dynamic reordering."
• Cudd_ShuffleHeap(manager, permutation): "Reorders variables according to given permutation."

By calling Cudd_AutodynDisable before declaring any variables, the variable levels will be initialized and remain in the order the variables are declared.

To address the more general case of obtaining some desired variable order at some arbitrary later time, first call Cudd_AutodynDisable, and then pass the desired variable order to Cudd_ShuffleHeap.

Examples of calling these functions can be found in the method dd.cudd.BDD.configure and in the function dd.cudd.reorder of the Python package dd, specifically in its Cython bindings to CUDD.

The variable order can be changed and reordering disabled using dd.cudd as follows:

from dd import cudd

bdd = cudd.BDD()
vrs = ['x', 'y', 'z']
bdd.declare(*vrs)
levels = {var: bdd.level_of_var(var) for var in vrs}
>>> levels
{'x': 0, 'y': 1, 'z': 2}
# change the levels
desired_levels = dict(x=2, y=0, z=1)
cudd.reorder(bdd, desired_levels)
# confirm that variables are now where desired
new_levels = {var: bdd.level_of_var(var) for var in vrs}
>>> new_levels
{'x': 2, 'y': 0, 'z': 1}
# dynamic reordering is initially turned on
>>> bdd.configure()
{'garbage_collection': True,
 'loose_up_to': 6710886,
 'max_cache_hard': 4294967295,
 'max_cache_soft': 4096,
 'max_growth': 1.2,
 'max_memory': 18446744073709551615,
 'max_swaps': 2000000,
 'max_vars': 1000,
 'min_hit': 30,
 'reordering': True}
# turn off dynamic reordering
bdd.configure(reordering=False)
# confirm dynamic reordering is now off
>>> bdd.configure()
{'garbage_collection': True,
 ...
 'reordering': False}  # here it is

---

Cudd_ReduceHeap invokes reordering, except for the special case that the choice CUDD_REORDER_NONE is given.

From Cudd_ReadReorderings's documentation:

However, calls that do not even initiate reordering are not counted. A call may not initiate reordering if there are fewer than minsize live nodes in the manager, or if CUDD_REORDER_NONE is specified as reordering method.