search

cjdrake / pyeda

Python EDA
BSD 2-Clause "Simplified" License
304 stars 54 forks source link

Reimplement DDs using C/C++ #105

Closed cjdrake closed 7 years ago

cjdrake commented 9 years ago

Most likely using CUDD.

johnyf commented 9 years ago

A suggestion would be to use the dd package. It is written in pure Python, and includes several standard algorithms, including reordering by sifting (CUDD's default).

A timing comparison using the N-queens problem produces the result below. In these runs, reordering was not used. In the future, reordering will be automatically invoked. (For example, the 9 queens instance results in a shared ROBDD that reaches >10**6 nodes).

It is planned to create (optional) bindings from dd to a C package, so that the user code can still be developed in Python (easy to debug and instrument), and then be used w/o changes for large problems. This will avoid duplication of effort.

A minor point is that dd is written in Python 2.7, but it shouldn't be too difficult to run it in Python 3 (e.g., using six).

comparison

cjdrake commented 9 years ago

Ioannis, thanks for the suggestion. This looks like a really neat library :+1:

johnyf commented 9 years ago

Thanks, dd == 0.1.1 has been released, and it includes (optional) Cython bindings to CUDD and BuDDy. The bindings look (almost) the same with the pure-Python interface (the one that automates reference counting), so they can be swapped w/o changes to user code. This allows distributing a pure-Python version, and deploying CUDD for problems whose size requires it.