This is a question about class design in SAGE. I'm going to implement classes for various flavors of decision diagrams using the outside package CUDD. It turns out that Cudd and its library is already part of SAGE -- it's included as part of Polybori (which uses it "under the covers"). The interface is in the directory SAGE_ROOT/include/cudd/cudd.h and the library is is in SAGE_ROOT/lib/libpboriCudd*
Decision diagrams are a particular implementation of Boolean Functions. They have some relation to things like BooleanPolynomialRing, but are definitely different. There are three main flavors of decision diagrams in Cudd: 1) Binary decision diagrams, or BDD's 2) Algebraic decision diagrams, or ADD' 3) Zero-suppressed binary decision diagrams, or ZDD's The first and the third are two different kind of implementations of functions from Boolean n-tuples to booleans. The second is an implementation of functions from Boolean n-tuples to some sort of algebraic system (usually the integers, or the reals, though sometimes it is a "tropical ring" -- as an aside do they exist in SAGE?). I would expect that a "correct" implementation of these objects would be somewhat analogous to the implementation of multivariate polynomials (or perhaps infinite polynomial rings -- since, using Cudd, one is allowed to add more variables dynamically). Cudd implements things by using was it calls a "manager". A manager is a large heap which contains variousl interconnected objects -- a mixture of all three of the above, with a fixed variable order for all of the objects there (variable order is critical in decision diagrams). Cudd has functions to convert betweeen the various objects, some of which can be considered standard coercions: BDD<--> ZDD BDD --> ADD but not ADD --> BDD (even though there are various conversions). In order to invoke such functions they must "live" in the same manager. Almost all of the calls to Cudd library functions need to pass a pointer to the manager that contains the objects. So I would expect some sort of class hierarchy: BooleanFunctionBase -- which would initialize a manager, and remember it. BDD, ADD and ZDD -- which would like a polynomial ring and BDDElement, ADDElement and ZDDElement The latter 3 would then allow various boolean operations betwee such elements, and allowing the automatic coercions that I described above. So the real question is what sort of things that I have to attend to in order to get the above implemented. In general, I would expect that most of the use of these functions would have everything using one global manager (would I use something in UniqueFactory for that?). However, I can imagine circumstances where one would like to use separate managers (since it's possible that the variable orders might need to be radically different). There's also the question of pickling, and extracting an external representation. I can't imagine that one could pickle things by saving the entire Cudd heap. Therefore it would also be necessary to have some sort of "external" representation. It turns out that all 3 DD's are represented by what amounts to a labeled DAG, so that representation makes the most sense. Using Cudd functions one can build up the Cudd internal representation from a DAG representation in time proportional to the number of nodes of the DAG. So, I would appreciate any specific advice about how I should do this. Victor -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
