Open SSoelvsten opened 1 year ago
Speaking with Andrew Miner, his implementation of MTBDDs use weights on each edge instead ( quite similar to QMDDs #443 ). Googling a little bit around, we may want to consider the following alternatives instead
This has the added benefit, that a lot of the meta data (e.g. cuts) does not need to be revised.
Right now, Adiar only supports diagrams, where the terminals (leaves) have boolean values. Of course, one can already use this to express non-boolean values by having b BDDs to represent each of the b bits individually. Yet, we can also extend the diagram itself to have non-boolean terminals, i.e. to make it a Multi-Terminal Binary Decision Diagrams (MTBDD) [Fujita97].
ptr
ptr_uint64
class currently has more than 32 bits available to store a terminal value. We can template this class to change what type and what content the value() function returns (assuming it fits within 32 bits).ptr_templ
class which is the "naive" version ofptr_uint64
where the level, data, out-index and flags are not encoded into a single 64-bit integer. One can make it slightly more reasonable in size by merging the flag and out-index into onechar
.node
The templating ofptr
should then be lifted to thenode
class.arc
An arc should be made variadic in theptr
type. This and the other two above can be done quite quickly.file
,writer
andstream
The templating ofnode
should then be lifted to theshared_levelized_file<node>
andshared_levelized_file<arc>
classes and their writers and readers. This meddles with some meta information that is only designed for binary terminals, e.g. cut sizes. This could take slightly longer, but they can probably quite nicely be resolved by generalising the idea of the different cut types.mtbdd
class Finally, all of the data types are done, and we can finally define themtbdd
class and that it uses different types of nodes. Now, we can pretty much reuse/generalise all of the BDD algorithm policies (strategies) to immediately obtain the algorithm for MTBDDs!mtbdd_restrict
is a 1-1 translation.mtbdd_apply
is also quite straightforward by just using an operator that works with non-booleans ( see also #162 )Of course, all of this ought to have some unit tests, such that we are sure we can trust the code.
References
Additional Context