Tag Line

PolyBoRi was created by man. There are two developers. And they have a plan.“

Saturday, July 20, 2013

GSOC 2013 project progress for weeks 0-4

I am Ioana Tamas, and this is a summary of the weekly updates of my GSOC 2013 project for Polybori.
Hopefully, the next updates will be posted in separate blog posts. My repository is: http://sourceforge.net/p/libzdd/code.

Weeks 0 &1:

I have been allocating a lot of time to learning how to work with big code bases etc., so the progress may not be very outstanding. Also, I figured that I will not be able to follow the proposed timeline, one example being the fact that updating the reference and memory allocation methods can't be done without updating the main classes and structures at the same time (which appear as later milestones).

Now, a summary of the code I have written until now:

1) I began the ZDD class, which will contain all the members and methods of the Cudd ZDD class, plus the ones inherited from Cudd classes that are of no use for Polybori (they were implemented in Cudd for handling more types of decision diagrams).

2) I started writing the structures needed for the completeness of the class definition, though I have not decided yet if I should rather have classes instead of structures. I also removed the structure members that are not useful for our purpose.

3) I have set up testing files, but I didn't include meaningful unit tests yet.

4) I added the Cudd code base in my directory, and I will gradually delete the files that are not useful until there is no Cudd left.

5) I made a namespace "libzdd" to avoid name coincidences. However, the way I did this may cause problems when I need Cudd files.

To finalize and summarize, the things I still have issues with would be:
- constructing the library using SCons, so that it accepts the boost unit test framework and takes into consideration the Cudd files
- correctly using the namespace
- choosing meaningful unit tests


During the past week, I started transforming the Cudd's structs into classes and further working on my main source and header file. After revising the timeline a little bit, I decided that I should take a break from what I started (so I temporarily commented a great part of my code) in order to work more on actually providing something that can be tested, using some temporary definitions. This part is still in progress.


The past week I temporarily kept only my Zero-Suppressed Decision Diagram class definition, using typedefs for the other relevant classes at the moment. This way, I was able to set up some boost tests and (more difficult than I expected) passing them. They test the things implemented until now, which are the constructors and some operators.

I also changed the structure of the repository, by making nice and clean header and source files for everything that I use currently use.

I also deleted a few things that I had introduced too early, but they will come back at the right time (they are saved somewhere in my computer for now).


This week, I made some significant progress in making the zdd_ZDD class (my project's main class) avoid using raw pointers, by wrapping the access to the Diagram Manager for all the constructors and operators.

In order to achieve this, I made use of boost shared pointers, and I introduced a new class.

I also introduced a unique table, with its own class (that will soon totally replace Cudd's), using boost tuples and std maps.

Tuesday, June 4, 2013

GSOC 2013 project for Polybori

I am Ioana-Maria Tamas and for this year's Google Summer of code, I will be working for lmonade's project: "Binary decision diagrams for Boolean polynomial rings". The main details of the project are the ones  below, but small modifications may occur.

  • Abstract

Zero-suppressed binary decision diagrams are used by Polybori for efficiently representing Boolean polynomials. At the moment, they are manipulated via CUDD, which is not specialized on this type of diagrams and only uses C in the implementation. The goal of the project is implementing an independent library in C++, that is specialized on  zero-suppressed binary decision diagrams.

  • Objective

There are no major problems in the current method used to deal with decision diagrams, but implementing the new library will definitely increase Polybori’s usability and efficiency. The things that will be reimplemented are the reference counting, the caching management, the diagram manager and then the operators and methods from the decision diagram class.

  • Deliverables

The final product will be a well-documented, well-tested and easy to build library, that will help Polybori manipulate Boolean Polynomials without using CUDD in the background, and in a more efficient and specialized way.

  • Timeline

    Time Frame
    17 June - 24 June
    Prepare unit tests for a wrapper class that works with CUDD in the background
    25 June - 5 July
    Implement a C++ reference counting method
    6 July - 11 July
    Add the new method to the wrapper and test
    12 July - 26 July
    Implement a C++ cache management method
    27 July - 2 August
    Add the new method to the wrapper and test
    Prepare for midterm evaluation
    3 August - 16 August
    Re-implement the DdManager, DdNode and DdChild and test them
    17 August - 31 August
    Implement a C++ ZDD class, with all the operations and methods available in CUDD
    1 September - 9 September
    Write unit tests that are independent from CUDD
    10 September - 15 September
    Optional: Make an independent C++ library using the new implementations (with a proper build system)
    Test everything without CUDD
    16 September - 23 September
    Finalize documentation
    Prepare for final evaluation

Wednesday, April 10, 2013

Release of PolyBoRi 0.8.3

Already some time ago we had released PolyBoRi 0.8.3 at
Among minor fixes it improves the support of multiple Python installations, comes with consistent library version naming, and easier updating of libm4ri. Binary packages for OpenSuse, Fedora, and Ubuntu are available at the usual place. Updated ebuild scripts for lmona.de and Gentoo-prefix as well as spkg packages for Sage will be available soon. Binary packages are available for recent OpenSuSE, and Fedora as well as Ubuntu distributions. Just point your package manager here:  

Updated ebuild scripts for lmona.de and Gentoo-prefix a will be available soon. 

Now, the updated spkg packages for Sage will be included in the next release. 

My best,