Set operations

In addition to polynomials POLYBORI implements a data type for sets of monomials, called BooleSet. This data type is also implemented on the top of ZDDs and allows to see polynomials from a different angle. Also, it makes high-level set operations possible, which are in most cases faster than operations handling individual terms, because the complexity of the algorithms depends only on the structure of the diagrams.

Polynomials can easily be converted to BooleSet s by using the member function set().

In [1]: f=x(2)*x(3)+x(1)*x(3)+x(2)+x(4)

In [2]: f
Out[2]: x(1)*x(3) + x(2)*x(3) + x(2) + x(4)

In [3]: f.set()
Out[3]: {{x(1),x(3)}, {x(2),x(3)}, {x(2)}, {x(4)}}
One of the most common operations is to split the set into cofactors of a variable. This illustrates the following example.
In [4]: s0=f.set().subset0(x(2).index())

In [5]: s0
Out[5]: {{x(1),x(3)}, {x(4)}}

In [6]: s1=f.set().subset1(x(2).index())

In [7]: s1
Out[7]: {{x(3)}, {}}

In [8]: f==Polynomial(s1)*x(2)+Polynomial(s0)
Out[8]: True

Even more low-level than operation with subset-methods is the use of navigators. Navigators provide an interface to diagram nodes, accessing their index as well as the corresponding then- and else-branches.

In [1]:f=x(1)*x(2)+x(2)*x(3)*x(4)+x(2)*x(4)+x(3)+x(4)+1

In [2]:s=f.set()

In [3]:s
Out[3]:{{x(1),x(2)}, {x(2),x(3),x(4)}, {x(2),x(4)}, {x(3)}, {x(4)}, {}}

In [4]:x(1).index()
Out[4]:1

In [5]:s.subset1(1)
Out[5]:{{x(2)}}

In [6]:s.subset0(1)
Out[6]:{{x(2),x(3),x(4)}, {x(2),x(4)}, {x(3)}, {x(4)}, {}}

In [7]:nav=s.navigation()

In [8]:BooleSet(nav,s.ring())
Out[8]:{{x(1),x(2)}, {x(2),x(3),x(4)}, {x(2),x(4)}, {x(3)}, {x(4)}, {}}

In [9]:nav.value()
Out[9]:1

In [10]:nav_else=nav.elseBranch()

In [11]:nav_else
Out[11]:<polybori.dynamic.PyPolyBoRi.CCuddNavigator object at 0xb6e1e7d4>

In [12]:BooleSet(nav_else,s.ring())
Out[12]:{{x(2),x(3),x(4)}, {x(2),x(4)}, {x(3)}, {x(4)}, {}}

In [13]:nav_else.value()
Out[13]:2

You should be very careful and always keep a reference to the original object, when dealing with navigators, as navigators contain only a raw pointer as data. For the same reason, it is necessary to supply the ring as argument, when constructing a set out of a navigator.

The opposite of navigation down a ZDD using navigators is to construct new ZDDs in the same way, namely giving their else- and then-branch as well as the index value of the new node.

    
In [1]:f0=x(2)*x(3)+x(3)

In [2]:f1=x(4)

In [3]:if_then_else(x(1),f0,f1)
Out[3]:{{x(1),x(2),x(3)}, {x(1),x(3)}, {x(4)}}

In [4]:if_then_else(x(1).index(),f0,f1)
Out[4]:{{x(1),x(2),x(3)}, {x(1),x(3)}, {x(4)}}

In [5]:if_then_else(x(5),f0,f1)
---------------------------------------------------------------------------
<type 'exceptions.ValueError'>            Traceback (most recent call last)

/home/user/PolyBoRi/<ipython console> in <module>()

<type 'exceptions.ValueError'>: Node index must be smaller than top indices of then- and
else-branch.

It is strictly necessary that the index of the created node is smaller than the index of the branches. But also operations on higher levels are possible, like the calculation of the minimal terms (with respect to division) in a BooleSet:

In [1]: f=x(2)*x(3)+x(1)*x(3)+x(2)+x(4)

In [2]: f.set()
Out[2]: {{x(1),x(3)}, {x(2),x(3)}, {x(2)}, {x(4)}}

In [3]: f.set().minimalElements()
Out[3]: {{x(1),x(3)}, {x(2)}, {x(4)}}
2011-02-25