Next: Programmer's Manual Up: CUDD: CU Decision Diagram Previous: How to Get CUDD Index

Subsections

Compiling and Linking
Basic Data Structures
Initializing and Shutting Down a DdManager
Setting Parameters
Constant Functions
Creating Variables
- New BDD and ADD Variables
- New ZDD Variables
Basic BDD Manipulation
Basic ADD Manipulation
Basic ZDD Manipulation
Converting ADDs to BDDs and Vice Versa
Converting BDDs to ZDDs and Vice Versa
Variable Reordering for BDDs and ADDs
Grouping Variables
Variable Reordering for ZDDs
Keeping Consistent Variable Orders for BDDs and ZDDs
Hooks
The SIS/VIS Interface
- Using the CUDD Package in SIS
Writing Decision Diagrams to a File
Saving and Restoring BDDs

User's Manual

This section describes the use of the CUDD package as a black box.

Compiling and Linking

To build an application that uses the CUDD package, you should add

#include "util.h"
#include "cudd.h"

to your source files, and should link libcudd.a, libmtr.a, libst.a, and libutil.a to your executable. (All these libraries are part of the distribution.) Some platforms require specific compiler and linker flags. Refer to the Makefile in the top level directory of the distribution.

Keep in mind that whatever flags affect the size of data structures--for instance the flags used to use 64-bit pointers where available--must be specified when compiling both CUDD and the files that include its header files.

Basic Data Structures

Nodes

BDDs, ADDs, and ZDDs are made of DdNode's. A DdNode (node for short) is a structure with several fields. Those that are of interest to the application that uses the CUDD package as a black box are the variable index, the reference count, and the value. The remaining fields are pointers that connect nodes among themselves and that are used to implement the unique table. (See Section 3.2.2.)

The index field holds the name of the variable that labels the node. The index of a variable is a permanent attribute that reflects the order of creation. Index 0 corresponds to the variable created first. On a machine with 32-bit pointers, the maximum number of variables is the largest value that can be stored in an unsigned short integer minus 1. The largest index is reserved for the constant nodes. When 64-bit pointers are used, the maximum number of variables is the largest value that can be stored in an unsigned integer minus 1.

When variables are reordered to reduce the size of the decision diagrams, the variables may shift in the order, but they retain their indices. The package keeps track of the variable permutation (and its inverse). The application is not affected by variable reordering, except in the following cases.

If the application uses generators (Cudd_ForeachCube and Cudd_ForeachNode ) and reordering is enabled, then it must take care not to call any operation that may create new nodes (and hence possibly trigger reordering). This is because the cubes (i.e., paths) and nodes of a diagram change as a result of reordering.
If the application uses Cudd_bddConstrain and reordering takes place, then the property of Cudd_bddConstrain of being an image restrictor is lost.

The CUDD package relies on garbage collection to reclaim the memory used by diagrams that are no longer in use. The scheme employed for garbage collection is based on keeping a reference count for each node. The references that are counted are both the internal references (references from other nodes) and external references (typically references from the calling environment). When an application creates a new BDD, ADD, or ZDD, it must increase its reference count explicitly, through a call to Cudd_Ref. Similarly, when a diagram is no longer needed, the application must call Cudd_RecursiveDeref (for BDDs and ADDs) or Cudd_RecursiveDerefZdd (for ZDDs) to ``recycle" the nodes of the diagram.

Terminal nodes carry a value. This is especially important for ADDs. By default, the value is a double. To change to something different (e.g., an integer), the package must be modified and recompiled. Support for this process is currently very rudimentary.

The Manager

All nodes used in BDDs, ADDs, and ZDDs are kept in special hash tables called the unique tables. Specifically, BDDs and ADDs share the same unique table, whereas ZDDs have their own table. As the name implies, the main purpose of the unique table is to guarantee that each node is unique; that is, there is no other node labeled by the same variable and with the same children. This uniqueness property makes decision diagrams canonical. The unique tables and some auxiliary data structures make up the DdManager (manager for short). Though the application that uses only the exported functions needs not be concerned with most details of the manager, it has to deal with the manager in the following sense. The application must initialize the manager by calling an appropriate function. (See Section 3.3.) Subsequently, it must pass a pointer to the manager to all the functions that operate on decision diagrams.

With the exception of a few statistical counters, there are no global variables in the CUDD package. Therefore, it is quite possible to have multiple managers simultaneously active in the same application.¹ It is the pointers to the managers that tell the functions on what data they should operate.

Cache

Efficient recursive manipulation of decision diagrams requires the use of a table to store computed results. This table is called here the cache because it is effectively handled like a cache of variable but limited capacity. The CUDD package starts by default with a small cache, and increases its size until either no further benefit is achieved, or a limit size is reached. The user can influence this policy by choosing initial and limit values for the cache size.

Too small a cache will cause frequent overwriting of useful results. Too large a cache will cause overhead, because the whole cache is scanned every time garbage collection takes place. The optimal parameters depend on the specific application. The default parameters work reasonably well for a large spectrum of applications.

The cache of the CUDD package is used by most recursive functions of the package, and can be used by user-supplied functions as well. (See Section 4.4.)

Initializing and Shutting Down a DdManager

To use the functions in the CUDD package, one has first to initialize the package itself by calling Cudd_Init. This function takes four parameters:

numVars: It is the initial number of variables for BDDs and ADDs. If the total number of variables needed by the application is known, then it is slightly more efficient to create a manager with that number of variables. If the number is unknown, it can be set to 0, or to any other lower bound on the number of variables. Requesting more variables than are actually needed is not incorrect, but is not efficient.
numVarsZ: It is the initial number of variables for ZDDs. See Sections 3.9 and 3.11 for a discussion of the value of this argument.
numSlots: Determines the initial size of each subtable of the unique table. There is a subtable for each variable. The size of each subtable is dynamically adjusted to reflect the number of nodes. It is normally O.K. to use the default value for this parameter, which is CUDD_UNIQUE_SLOTS.
cacheSize: It is the initial size (number of entries) of the cache. Its default value is CUDD_CACHE_SLOTS.
maxMemory: It is the target value for the maximum memory occupation (in bytes). The package uses this value to decide two parameters.
- the maximum size to which the cache will grow, regardless of the hit rate or the size of the unique table.
- the maximum size to which growth of the unique table will be preferred to garbage collection.
If maxMemory is set to 0, CUDD tries to guess a good value based on the available memory.

A typical call to Cudd_Init may look like this:

  manager = Cudd_Init(0,0,CUDD_UNIQUE_SLOTS,CUDD_CACHE_SLOTS,0);

To reclaim all the memory associated with a manager, an application must call Cudd_Quit. This is normally done before exiting.

Setting Parameters

The package provides several functions to set the parameters that control various functions. For instance, the package has an automatic way of determining whether a larger unique table would make the application run faster. In that case, the package enters a ``fast growth" mode in which resizing of the unique subtables is favored over garbage collection. When the unique table reaches a given size, however, the package returns to the normal ``slow growth" mode, even though the conditions that caused the transition to fast growth still prevail. The limit size for fast growth can be read by Cudd_ReadLooseUpTo and changed by Cudd_SetLooseUpTo. Similar pairs of functions exist for several other parameters. See also Section 4.8.

Constant Functions

The CUDD Package defines several constant functions. These functions are created when the manager is initialized, and are accessible through the manager itself.

One, Logic Zero, and Arithmetic Zero

The constant 1 (returned by Cudd_ReadOne) is common to BDDs, ADDs, and ZDDs. However, its meaning is different for ADDs and BDDs, on the one hand, and ZDDs, on the other hand. The diagram consisting of the constant 1 node only represents the constant 1 function for ADDs and BDDs. For ZDDs, its meaning depends on the number of variables: It is the conjunction of the complements of all variables. Conversely, the representation of the constant 1 function depends on the number of variables. The constant 1 function of variables is returned by Cudd_ReadZddOne.

The constant 0 is common to ADDs and ZDDs, but not to BDDs. The BDD logic 0 is not associated with the constant 0 function: It is obtained by complementation ( Cudd_Not) of the constant 1. (It is also returned by Cudd_ReadLogicZero.) All other constants are specific to ADDs.

Predefined Constants

Besides 0 (returned by Cudd_ReadZero) and 1, the following constant functions are created at initialization time.

PlusInfinity and MinusInfinity: On computers implementing the IEEE standard 754 for floating-point arithmetic, these two constants are set to the signed infinities. On the DEC Alphas, the option -ieee_with_no_inexact or -ieee_with_inexact must be passed to the DEC compiler to get support of the IEEE standard. (The compiler still produces a warning, but it can be ignored.) Compiling with those options may cause substantial performance degradation on the Evolution IV CPUs. (Especially if the application does use the infinities.) The problem is reportedly solved in the Evolution V CPUs. If gcc is used to compile CUDD on the Alphas, the symbol HAVE_IEEE_754 must be undefined. (See the Makefile for the details.) The values of these constants are returned by Cudd_ReadPlusInfinity and Cudd_ReadMinusInfinity.
Epsilon: This constant, initially set to $10^{-12}$ , is used in comparing floating point values for equality. Its value is returned by Cudd_ReadEpsilon, and it can be modified by calling Cudd_SetEpsilon. Unlike the other constants, it does not correspond to a node.

Background

The background value is a constant typically used to represent non-existing arcs in graphs. Consider a shortest path problem. Two nodes that are not connected by an arc can be regarded as being joined by an arc of infinite length. In shortest path problems, it is therefore convenient to set the background value to PlusInfinity. In network flow problems, on the other hand, two nodes not connected by an arc can be regarded as joined by an arc of 0 capacity. For these problems, therefore, it is more convenient to set the background value to 0. In general, when representing sparse matrices, the background value is the value that is assumed implicitly.

At initialization, the background value is set to 0. It can be read with Cudd_ReadBackground, and modified with Cudd_SetBackground. The background value affects procedures that read sparse matrices/graphs ( Cudd_addRead and Cudd_addHarwell), procedures that print out sum-of-product expressions for ADDs ( Cudd_PrintMinterm), generators of cubes (Cudd_ForeachCube), and procedures that count minterms ( Cudd_CountMinterm).

New Constants

New constant can be created by calling Cudd_addConst. This function will retrieve the ADD for the desired constant, if it already exist, or it will create a new one. Obviously, new constants should only be used when manipulating ADDs.

Creating Variables

Decision diagrams are typically created by combining simpler decision diagrams. The simplest decision diagrams, of course, cannot be created in that way. Constant functions have been discussed in Section 3.5. In this section we discuss the simple variable functions, also known as projection functions.

New BDD and ADD Variables

The projection functions are distinct for BDDs and ADDs. A projection function for BDDs consists of an internal node with both outgoing arcs pointing to the constant 1. The else arc is complemented.

An ADD projection function, on the other hand, has the else pointer directed to the arithmetic zero function. One should never mix the two types of variables. BDD variables should be used when manipulating BDDs, and ADD variables should be used when manipulating ADDs. Three functions are provided to create BDD variables:

Cudd_bddIthVar: Returns the projection function with index . If the function does not exist, it is created.
Cudd_bddNewVar: Returns a new projection function, whose index is the largest index in use at the time of the call, plus 1.
Cudd_bddNewVarAtLevel: Similar to Cudd_bddNewVar. In addition it allows to specify the position in the variable order at which the new variable should be inserted. By contrast, Cudd_bddNewVar adds the new variable at the end of the order.

The analogous functions for ADDs are Cudd_addIthVar, Cudd_addNewVar, and Cudd_addNewVarAtLevel.

New ZDD Variables

Unlike the projection functions of BDDs and ADDs, the projection functions of ZDDs have diagrams with nodes, where is the number of variables. Therefore the ZDDs of the projection functions change when new variables are added. This will be discussed in Section 3.9. Here we assume that the number of variables is fixed. The ZDD of the -th projection function is returned by Cudd_zddIthVar.

Basic BDD Manipulation

Common manipulations of BDDs can be accomplished by calling Cudd_bddIte. This function takes three BDDs, , , and , as arguments and computes $f\cdot g + f'\cdot h$ . Like all the functions that create new BDDs or ADDs, Cudd_bddIte returns a result that must be explicitly referenced by the caller. Cudd_bddIte can be used to implement all two-argument boolean functions. However, the package also provides Cudd_bddAnd as well as the other two-operand boolean functions, which are slightly more efficient when a two-operand function is called for. The following fragment of code illustrates how to build the BDD for the function .

        DdManager *manager;
        DdNode *f, *var, *tmp;
        int i;

        ...

        f = Cudd_ReadOne(manager);
        Cudd_Ref(f);
        for (i = 3; i >= 0; i--) {
            var = Cudd_bddIthVar(manager,i);
            tmp = Cudd_bddAnd(manager,Cudd_Not(var),f);
            Cudd_Ref(tmp);
            Cudd_RecursiveDeref(manager,f);
            f = tmp;
        }

This example illustrates the following points:

Intermediate results must be ``referenced" and ``dereferenced." However, var is a projection function, and its reference count is always greater than 0. Therefore, there is no call to Cudd_Ref.
The new f must be assigned to a temporary variable ( tmp in this example). If the result of Cudd_bddAnd were assigned directly to f, the old f would be lost, and there would be no way to free its nodes.
The statement f = tmp has the same effect as:
```
            f = tmp;
            Cudd_Ref(f);
            Cudd_RecursiveDeref(manager,tmp);
```
but is more efficient. The reference is ``passed" from tmp to f, and tmp is now ready to be reutilized.
It is normally more efficient to build BDDs ``bottom-up." This is why the loop goes from 3 to 0. Notice, however, that after variable reordering, higher index does not necessarily mean ``closer to the bottom." Of course, in this simple example, efficiency is not a concern.
Had we wanted to conjoin the variables in a bottom-up fashion even after reordering, we should have used Cudd_ReadInvPerm. One has to be careful, though, to fix the order of conjunction before entering the loop. Otherwise, if reordering takes place, it is possible to use one variable twice and skip another variable.

Basic ADD Manipulation

The most common way to manipulate ADDs is via Cudd_addApply. This function can apply a wide variety of operators to a pair of ADDs. Among the available operators are addition, multiplication, division, minimum, maximum, and boolean operators that work on ADDs whose leaves are restricted to 0 and 1 (0-1 ADDs).

The following fragment of code illustrates how to build the ADD for the function .

        DdManager *manager;
        DdNode *f, *var, *tmp;
        int i;

        ...

        f = Cudd_addConst(manager,5);
        Cudd_Ref(f);
        for (i = 3; i >= 0; i--) {
            var = Cudd_addIthVar(manager,i);
            Cudd_Ref(var);
            tmp = Cudd_addApply(manager,Cudd_addTimes,var,f);
            Cudd_Ref(tmp);
            Cudd_RecursiveDeref(manager,f);
            Cudd_RecursiveDeref(manager,var);
            f = tmp;
        }

This example, contrasted to the example of BDD manipulation, illustrates the following points:

The ADD projection function are not maintained by the manager. It is therefore necessary to reference and dereference them.
The product of two ADDs is computed by calling Cudd_addApply with Cudd_addTimes as parameter. There is no ``apply'' function for BDDs, because Cudd_bddAnd and Cudd_bddXor plus complementation are sufficient to implement all two-argument boolean functions.

Basic ZDD Manipulation

ZDDs are often generated by converting existing BDDs. (See Section 3.11.) However, it is also possible to build ZDDs by applying boolean operators to other ZDDs, starting from constants and projection functions. The following fragment of code illustrates how to build the ZDD for the function . We assume that the four variables already exist in the manager when the ZDD for is built. Note the use of De Morgan's law.

        DdManager *manager;
        DdNode *f, *var, *tmp;
        int i;

        manager = Cudd_Init(0,4,CUDD_UNIQUE_SLOTS,
                            CUDD_CACHE_SLOTS,0);
        ...

        tmp = Cudd_ReadZddOne(manager,0);
        Cudd_Ref(tmp);
        for (i = 3; i >= 0; i--) {
            var = Cudd_zddIthVar(manager,i);
            Cudd_Ref(var);
            f = Cudd_zddIntersect(manager,var,tmp);
            Cudd_Ref(f);
            Cudd_RecursiveDerefZdd(manager,tmp);
            Cudd_RecursiveDerefZdd(manager,var);
            tmp = f;
        }
        f = Cudd_zddDiff(manager,Cudd_ReadZddOne(manager,0),tmp);
        Cudd_Ref(f);
        Cudd_RecursiveDerefZdd(manager,tmp);

This example illustrates the following points:

The projection functions are referenced, because they are not maintained by the manager.
Complementation is obtained by subtracting from the constant 1 function.
The result of Cudd_ReadZddOne does not require referencing.

CUDD provides functions for the manipulation of covers represented by ZDDs. For instance, Cudd_zddIsop builds a ZDD representing an irredundant sum of products for the incompletely specified function defined by the two BDDs

and

. Cudd_zddWeakDiv performs the weak division of two covers given as ZDDs. These functions expect the two ZDD variables corresponding to the two literals of the function variable to be adjacent. One has to create variable groups (see Section 3.14) for reordering of the ZDD variables to work. BDD automatic reordering is safe even without groups: If realignment of ZDD and ADD/BDD variables is requested (see Section 3.15) groups will be kept adjacent.

Converting ADDs to BDDs and Vice Versa

Several procedures are provided to convert ADDs to BDDs, according to different criteria. ( Cudd_addBddPattern, Cudd_addBddInterval, and Cudd_addBddThreshold.) The conversion from BDDs to ADDs ( Cudd_BddToAdd) is based on the simple principle of mapping the logical 0 and 1 on the arithmetic 0 and 1. It is also possible to convert an ADD with integer values (more precisely, floating point numbers with 0 fractional part) to an array of BDDs by repeatedly calling Cudd_addIthBit.

Converting BDDs to ZDDs and Vice Versa

Many applications first build a set of BDDs and then derive ZDDs from the BDDs. These applications should create the manager with 0 ZDD variables and create the BDDs. Then they should call Cudd_zddVarsFromBddVars to create the necessary ZDD variables--whose number is likely to be known once the BDDs are available. This approach eliminates the difficulties that arise when the number of ZDD variables changes while ZDDs are being built.

The simplest conversion from BDDs to ZDDs is a simple change of representation, which preserves the functions. Simply put, given a BDD for , a ZDD for is requested. In this case the correspondence between the BDD variables and ZDD variables is one-to-one. Hence, Cudd_zddVarsFromBddVars should be called with the multiplicity parameter equal to 1. The conversion proper can then be performed by calling Cudd_zddPortFromBdd. The inverse transformation is performed by Cudd_zddPortToBdd.

ZDDs are quite often used for the representation of covers. This is normally done by associating two ZDD variables to each variable of the function. (And hence, typically, to each BDD variable.) One ZDD variable is associated with the positive literal of the BDD variable, while the other ZDD variable is associated with the negative literal. A call to Cudd_zddVarsFromBddVars with multiplicity equal to 2 will associate to BDD variable the two ZDD variables and .

If a BDD variable group tree exists when Cudd_zddVarsFromBddVars is called (see Section 3.13) the function generates a ZDD variable group tree consistent to it. In any case, all the ZDD variables derived from the same BDD variable are clustered into a group.

If the ZDD for is created and later a new ZDD variable is added to the manager, the function represented by the existing ZDD changes. Suppose, for instance, that two variables are initially created, and that the ZDD for is built. If a third variable is added, say , then the ZDD represents instead. This change in function obviously applies regardless of what use is made of the ZDD. However, if the ZDD is used to represent a cover, the cover itself is not changed by the addition of new variable. (What changes is the characteristic function of the cover.)

Variable Reordering for BDDs and ADDs

The CUDD package provides a rich set of dynamic reordering algorithms. Some of them are slight variations of existing techniques [16,6,2,10,15,11]; some others have been developed specifically for this package [14,13].

Reordering affects a unique table. This means that BDDs and ADDs, which share the same unique table are simultaneously reordered. ZDDs, on the other hand, are reordered separately. In the following we discuss the reordering of BDDs and ADDs. Reordering for ZDDs is the subject of Section 3.14.

Reordering of the variables can be invoked directly by the application by calling Cudd_ReduceHeap. Or it can be automatically triggered by the package when the number of nodes has reached a given threshold. (The threshold is initialized and automatically adjusted after each reordering by the package.) To enable automatic dynamic reordering (also called asynchronous dynamic reordering in this document) the application must call Cudd_AutodynEnable. Automatic dynamic reordering can subsequently be disabled by calling Cudd_AutodynDisable.

All reordering methods are available in both the case of direct call to Cudd_ReduceHeap and the case of automatic invocation. For many methods, the reordering procedure is iterated until no further improvement is obtained. We call these methods the converging methods. When constraints are imposed on the relative position of variables (see Section 3.13) the reordering methods apply inside the groups. The groups themselves are reordered by sifting. Each method is identified by a constant of the enumerated type Cudd_ReorderingType defined in cudd.h (the external header file of the CUDD package):

CUDD_REORDER_NONE:: This method causes no reordering.
CUDD_REORDER_SAME:: If passed to Cudd_AutodynEnable, this method leaves the current method for automatic reordering unchanged. If passed to Cudd_ReduceHeap, this method causes the current method for automatic reordering to be used.
CUDD_REORDER_RANDOM:: Pairs of variables are randomly chosen, and swapped in the order. The swap is performed by a series of swaps of adjacent variables. The best order among those obtained by the series of swaps is retained. The number of pairs chosen for swapping equals the number of variables in the diagram.
CUDD_REORDER_RANDOM_PIVOT:: Same as CUDD_REORDER_RANDOM, but the two variables are chosen so that the first is above the variable with the largest number of nodes, and the second is below that variable. In case there are several variables tied for the maximum number of nodes, the one closest to the root is used.
CUDD_REORDER_SIFT:: This method is an implementation of Rudell's sifting algorithm [16]. A simplified description of sifting is as follows: Each variable is considered in turn. A variable is moved up and down in the order so that it takes all possible positions. The best position is identified and the variable is returned to that position.
In reality, things are a bit more complicated. For instance, there is a limit on the number of variables that will be sifted. This limit can be read with Cudd_ReadSiftMaxVar and set with Cudd_SetSiftMaxVar. In addition, if the diagram grows too much while moving a variable up or down, that movement is terminated before the variable has reached one end of the order. The maximum ratio by which the diagram is allowed to grow while a variable is being sifted can be read with Cudd_ReadMaxGrowth and set with Cudd_SetMaxGrowth.
CUDD_REORDER_SIFT_CONVERGE:: This is the converging variant of CUDD_REORDER_SIFT.
CUDD_REORDER_SYMM_SIFT:: This method is an implementation of symmetric sifting [14]. It is similar to sifting, with one addition: Variables that become adjacent during sifting are tested for symmetry. If they are symmetric, they are linked in a group. Sifting then continues with a group being moved, instead of a single variable. After symmetric sifting has been run, Cudd_SymmProfile can be called to report on the symmetry groups found. (Both positive and negative symmetries are reported.)
CUDD_REORDER_SYMM_SIFT_CONV:: This is the converging variant of CUDD_REORDER_SYMM_SIFT.
CUDD_REORDER_GROUP_SIFT:: This method is an implementation of group sifting [13]. It is similar to symmetric sifting, but aggregation is not restricted to symmetric variables.
CUDD_REORDER_GROUP_SIFT_CONV:: This method repeats until convergence the combination of CUDD_REORDER_GROUP_SIFT and CUDD_REORDER_WINDOW4.
CUDD_REORDER_WINDOW2:: This method implements the window permutation approach of Fujita [8] and Ishiura [10]. The size of the window is 2.
CUDD_REORDER_WINDOW3:: Similar to CUDD_REORDER_WINDOW2, but with a window of size 3.
CUDD_REORDER_WINDOW4:: Similar to CUDD_REORDER_WINDOW2, but with a window of size 4.
CUDD_REORDER_WINDOW2_CONV:: This is the converging variant of CUDD_REORDER_WINDOW2.
CUDD_REORDER_WINDOW3_CONV:: This is the converging variant of CUDD_REORDER_WINDOW3.
CUDD_REORDER_WINDOW4_CONV:: This is the converging variant of CUDD_REORDER_WINDOW4.
CUDD_REORDER_ANNEALING:: This method is an implementation of simulated annealing for variable ordering, vaguely resemblant of the algorithm of [2]. This method is potentially very slow.
CUDD_REORDER_GENETIC:: This method is an implementation of a genetic algorithm for variable ordering, inspired by the work of Drechsler [6]. This method is potentially very slow.
CUDD_REORDER_EXACT:: This method implements a dynamic programming approach to exact reordering [9,7,10], with improvements described in [11]. It only stores one BDD at the time. Therefore, it is relatively efficient in terms of memory. Compared to other reordering strategies, it is very slow, and is not recommended for more than 16 variables.

So far we have described methods whereby the package selects an order automatically. A given order of the variables can also be imposed by calling Cudd_ShuffleHeap.

Grouping Variables

CUDD allows the application to specify constraints on the positions of group of variables. It is possible to request that a group of contiguous variables be kept contiguous by the reordering procedures. It is also possible to request that the relative order of some groups of variables be left unchanged. The constraints on the order are specified by means of a tree, which is created in one of two ways:

By calling Cudd_MakeTreeNode.
By calling the functions of the MTR library (part of the distribution), and by registering the result with the manager using Cudd_SetTree. The current tree registered with the manager can be read with Cudd_ReadTree.

Each node in the tree represents a range of variables. The lower bound of the range is given by the low field of the node, and the size of the group is given by the size field of the node.² The variables in each range are kept contiguous. Furthermore, if a node is marked with the MTR_FIXED flag, then the relative order of the variable ranges associated to its children is not changed. As an example, suppose the initial variable order is:

        x0, y0, z0, x1, y1, z1, ... , x9, y9, z9.