trolando / sylvan

Implementation of multi-core (binary) decision diagrams
Apache License 2.0
67 stars 29 forks source link

Recursive implementation of zdd_eval #35

Open marek-zeleny opened 1 year ago

marek-zeleny commented 1 year ago

I have re-implemented the zdd_eval() operator to work also in the general case, i.e. for variables that are not in the root of the evaluated ZDD. The algorithm is taken from the following paper, where it's called subset0, resp. subset1:

Shin-ichi Minato. 1993. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the 30th international Design Automation Conference (DAC '93). Association for Computing Machinery, New York, NY, USA, 272–277. https://doi.org/10.1145/157485.164890

I have also added some test cases for this operation and have since used it as a subroutine in other algorithms, where it seems to be yielding correct results. I hope I have correctly used the library's internals (caching, protection from GC, ...).

trolando commented 6 months ago

I'll check this out later, what is the purpose of this version? I.e. use case?