next up previous index
Next: Creating Variables Up: User's Manual Previous: Setting Parameters

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, Logical 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 n variables is returned by Cudd_ReadZddOne .

The constant 0 is common to ADDs and ZDDs, but not to BDDs. The BDD  logical 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_ReadLogicalZero .) 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.

  1. 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 .
  2. Epsilon : This constant, initially set to tex2html_wrap_inline2270, 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.


next up previous index
Next: Creating Variables Up: User's Manual Previous: Setting Parameters

Fabio Somenzi
Tue May 12 18:47:58 MDT 1998