New in Version 0.15.1 (released 09 Jul 2019)

Simple Interface Changes

  • For forests with range of INTEGER, function values are now long instead of int. The interface has been updated appropriately (methods createEdge, createEdgeForVar, and evaluate).

Expert Interface Changes

The compute table interface has changed significantly. This will affect anyone who implements their own operations. Essentially, the compute table is now much more aware of the contents of each compute table entry (in terms of the types of items in an entry). The long term goals of this change include simplification (and better flexibility flexibility) of operation code and eventually to allow for efficient compression of compute table entries.

  • Class compute_table::search_key has been renamed compute_table::entry_key, and is now concrete.

  • Class compute_table::search_result has been renamed compute_table::entry_result, and is now concrete.

  • Class compute_table::entry_builder has been removed. A compute table entry is now added by giving the key portion and the result portion.

  • New class, compute_table::entry_type with type information for compute table entries.

  • The list of recycled entry_keys is now maintained in class compute_table. When implementing an operation, old code: 
    compute_table::entry_key* CTsrch = useCTkey();
CTsrch->reset();
// ...
doneCTkey(CTsrch);

    should be replaced with:

    compute_table::entry_key* CTsrch = CT->useEntryKey(this);
// ...
CT->recycle(CTsrch);

  • Instead of returning the result, the compute_table::find method now expects the result to be passed as an argument and will be filled in. Operations now pre-allocate results for this purpose (only one result is needed per entry type).

  • Removed OperationMap as a compute table option.

Implementation

  • Streamlined compute table implemenation using templates.

New in Version 0.15.0 (released 22 May 2018)

We have changed the release numbering system, because the repository has moved to git and the old version numbering system was based on the Subversion revision number.

Simple Interface Changes

  • New (experimental) method, dd_edge::writePicture, generates a visualization of the decision diagram. You must have Graphviz installed for this to work.

Expert Interface Changes

  • Various improvements and extensions to Saturation implementation.

Implementation Changes

  • Moved node_headers out of expert_forest.
  • Node header now includes incoming count.
  • Separated memory management out of node storage, into its own style that can be set at runtime.
  • Error class now tracks filename and line number of source code that threw the error.
  • Updated garbage collection of compute table entries. Compute table entry status is now one of: dead, recoverable, active.
  • Support for extensible variables:
    • To enable, give the variable a negative bound
    • Can mix extensible and non-extensible variables in the same domain
    • Supported in multi-terminal forests for sets and relations
    • Compatible with Apply operations and saturation

New in Version 0.14.818 (released 05 Jul 2017)

Simple Interface Changes

  • Class node_storage factory portion split into new class, node_storage_style. Interface updated.
  • Forest policies must be constructed after library initialization, because node storage styles will not be known before this. A new empty constructor, and method useDefaults, have been added to class forest::policies to allow this.
  • Changed error code OVERFLOW to VALUE_OVERFLOW to avoid name issues with math macro.

Expert Interface Changes

  • Default policies for MDD and MXD forests moved from class settings to class forest as static members. This allows the defaults to be changed after library initialization.
  • Initialization sequence has been removed from class settings, and is instead passed to the MEDDLY initialization function explicitly.
  • Class op_initializer has been converted into a generic library initialization class, initializer_list.
  • Class cleanup_procedure has been removed; use initializer_list instead.
  • Compute table initialization is now handled by an initializer, class ct_initializer. The compute table settings have been moved from class settings, and into this new class. To change the default compute table settings, you should
    1. Build and save the default initializer list, using defaultInitializerList().
    2. Change the compute table settings, using static methods of class ct_initializer.
    3. Initialize the library, using the initializer list that was saved in step 1.
  • The old class settings has been removed, since it has become empty.

Implementation Changes

  • Node storage styles are now set up using an initializer_list.

New in Version 0.13.685 (released 15 Jun 2016)

Simple Interface Changes

  • New abstract interfaces for I/O (classes input and output) for all library I/O (except for internal debugging I/O). Use classes FILE_input and FILE_output for C-style FILE* I/O, and classes istream_input and ostream_output for C++-style iostream I/O. meddly.h now includes both cstdio and iostream. These can be disabled if necessary by defining _MEDDLY_WITHOUT_CSTDIO_ or _MEDDLY_WITHOUT_IOSTREAM_, respectively, before including meddly.h.

Expert Interface Changes

  • Class node_reader is now class unpacked_node, and methods to initialize a node reader have been moved into the unpacked_node class.
  • Class node_builder has been eliminated; all functionality has been moved to class unpacked_node.
  • Class node_header is now a private inner class for class expert_forest; all access to node header information should be through getter and setter helper functions.
  • Prototype implementation of saturation on partitioned transition relations. See operation SATURATION_FORWARD and class satpregen_opname.
  • Prototype implementation of on-the-fly saturation. See operation SATURATION_OTF_FORWARD and class satotf_opname.

Implementation Changes

  • Fixed several bugs with node reference counts.

New in Version 0.12.625 (released 25 Apr 2015)

Simple Interface Changes

  • More careful and more strict use of set methods in class dd_edge: for multi-terminal forests, use set with a single argument; for edge-valued forsts, use the appropriate two-argument version of set.
  • Added new edge labeling possiblity, INDEX_SET. From now on, this should be used instead of EVPLUS whenever an indexed set is constructed with operation CONVERT_TO_INDEX_SET, otherwise the library will throw an exception.
  • Added operations VM_MULTIPLY, MV_MULTIPLY and MM_MULTIPLY for MTMxDs.
  • Changed design of the enumerator class. Regular enumerators can be initialized as usual (constructor with a dd_edge). Otherwise, use a constructor (or initialize later) by passing the enumeration type and forest. Note that now, the forest for an enumerator is fixed for its life.
  • Added support for EV*MxDs.
  • Added mechanism to log forest changes to a file, to be utilized by other utilities (see class logger within class forest).
  • Cleaned up the header file.

Expert Interface Changes

  • Added classes int_EVencoder and float_EVencoder for a centralized mechanism for storing edge values within nodes.
  • Classes bool_encoder, int_encoder, and float_encoder have been renamed bool_Tencoder, int_Tencoder, and float_Tencoder for consistency.
  • Vector-matrix and matrix-vector multiply can now use INDEX_SET or EVPLUS forests. Currently, it is better to use INDEX_SET forests if possible.
  • Changed names VECT_MATR_MULT and MATR_VECT_MULT, to EXPLVECT_MATR_MULT and MATR_EXPLVECT_MULT, to emphasize that vectors are stored explicitly.
  • Completely re-designed the compute table interface. Large impact on implementation of operations; little to no impact on everything else. The new interface completely hides the compute table storage mechanism, so we will be able to plug in different storage schemes without changing any operation code (at least, in theory). Part of the gradual shift toward 64-bit node handles.
  • Class numerical_operation is removed and should be replaced by specialized_operation.
  • Added a specialized_operation for saturation, which allows the use of partitioned transition relations with options for organizing and combining them. See class satpregen_opname, and SATURATION_FORWARD.
  • Cleaned up the header file.

Implementation Changes

  • New implementation of COPY. It should now be possible to copy between almost any two forests over the same domain (assuming they are either both for sets, or both for relations).
  • Added test applications for COPY, and EV*MxDs.

New in Version 0.11.486 (released 04 Feb 2014)

Simple Interface Changes

  • Added const to array of terminal values, in parameter to createEdgeForVar methods. This should have minimal, if any, impact on applications.
  • Added constants DONT_CARE and DONT_CHANGE, which should be used instead of raw values, for calls to createEdge() methods. In particular, DONT_CHANGE should NOT be used for unprimed levels.

Expert Interface Changes

The mechanism for encoding and decoding terminal nodes (for multi-terminal forests) has been changed. The following methods of expert_forest were removed:

  • getBoolean()
  • getInteger()
  • getReal()
  • getTerminalNode()
  • isValidTerminalValue()

Terminal encoding is now handled by classes bool_encoder, int_encoder, and float_encoder inside expert_forest, allowing the use of templates if desired. The following methods have been added for convenience:

  • handleForValue()
  • getValueFromHandle()
  • getBooleanFromHandle()
  • getIntegerFromHandle()
  • getRealFromHandle()

Implementation Changes

  • Reorganized (and reimplemented) mutli-terminal hierarchy
  • A few bug fixes

New in Version 0.10.456 (released 30 Jul 2013)

  • Added typedefs for node handles and addresses, updated the interface and code to use these.
  • Switched to one pool of nodes per forest, instead of one pool per level.
  • Changed free list representation for node handles.
  • The node storage mechanism is now loosely coupled, and may be selected at runtime.
  • The node memory recycling mechanism is now loosely coupled. There are a few mechanisms to choose from.
  • Added a new node storage mechanism that uses compression.
  • Added ability to read and write DDs to a file.

Simple Interface Changes

  • The forest policy for specifying full vs sparse node storage has changed. Now, this is specified via storage_flags by combining flags ALLOW_FULL_STORAGE and ALLOW_SPARSE_STORAGE as appropriate.
  • The node storage scheme may be changed on a per forest basis, at runtime, by setting the forest policy as appropriate (member nodestor).
  • Removed forest policy recycleNodeStorageHoles, since the new policy nodestor allows to specify how nodes are stored and how holes are tracked (if at all).
  • In the forest class, added methods
    • writeEdges, to write one or more edges (and all nodes below) to a file in a machine readable format
    • readEdges, to read one or more edges (and all nodes below) from a file

Expert Interface Changes

  • The node storage interface has changed. This is likely to affect forest implementations, and not much else.
  • Different node storage schemes are implemented in the storage subdirectory. Motivated users may invent and use their own schemes.
  • In the expert_forest class, method reportMemoryUsage has been replaced by method reportStats.
  • expert_forest::markNodesInSubgraph and expert_forest::showNodeGraph now take an array of root nodes, instead of a single one.

New in Version 0.9.397 (released 26 Jul 2012)

  • New unique table.
  • New iterator implementation for dd_edge class.
  • Using fine-grained identity reduction rules.
  • Lots of code reorganization and cleanup.

Simple Interface Changes

  • Iterators have been replaced with enumerators. The old code segment 
    for (dd_edge::const_iterator i = e.begin(); i; ++i)

    should be replaced by

    for (enumerator i(e); i; ++i)

    and most other iterator functionality has been included in the enumerator class.

  • Removed findFirstElement methods, the same behavior can be obtained with enumerators.

  • Removed createSubmatrix methods, the same behavior can be obtained with the cross product and intersection operators.

Expert Interface Changes

  • Added node_builder subclass, updated operations to use it. This is the mechanism to use for building new nodes.

  • Added node_reader subclass, updated operations to use it. This is the mechanism to use for reading nodes in a forest.

  • Removed most of the old interface for accessing nodes.

  • Removed temporary edges.

New in Version 0.8.311 (released 18 Jun 2012)

  • Improved documentation generation (automatically updates library version number).
  • Added complete technical documentation under a new docs-devel directory.
  • Reorganized forest class hierarchy, in directory src/forests.
  • More thorough library cleanup in MEDDLY::cleanup().
  • New version of MULTIPLY identifies more terminal cases.

Interface Changes

  • Policy settings for a forest are now specified when the forest is constructed. The old code segment 
    forest *f = d->createForest(false, forest::BOOLEAN, forest::MULTI_TERMINAL);
f->setReductionRule(forest::FULLY_REDUCED);
f->setNodeStorage(forest::FULL_OR_SPARSE_STORAGE);
f->setNodeDeletion(forest::PESSIMISTIC_DELETION);

    can be replaced by

    forest::policies fp(false); // false: not a relation
fp.setFullyReduced();
fp.setCompactStorage();
fp.setPessimistic();
forest *f = d->createForest(false, forest::BOOLEAN, forest::MULTI_TERMINAL, fp);

    The default settings for the forest::policies struct may be found by examining the header file meddly.h, and of course it is only necessary to specify a desired policy that differs from its default. Alternatively, a forest may be created using

    forest *f = d->createForest(false, forest::BOOLEAN, forest::MULTI_TERMINAL);

    which will use the library-wide default policies, based on whether the new forest is a relation or not. The library-wide defaults, if not specified, will be equal to the default forest::policies initialization; otherwise, they may be changed by adjusting mddDefaults and mxdDefaults in MEDDLY::settings (in the expert interface) before the library is initialized.

  • In class domain, old methods getVar and readVar are changed to useVar and getVar, for consistency.

  • Added a better statistics mechanism for forests. The old interface is stil present, for compatability. More information may be obtained using forest::getStats().

New in Version 0.7.254 (released 15 Jul 2011)

  • No changes to the simple interface.
  • The compute table class is now visible in the expert interface. This should allow operations to be defined outside the library and still use the built-in compute tables.
  • The compute table mechanism has been redesigned and reimplemented. The compute table interface has changed significantly; this will affect anyone who implements their own operations.
  • Different compute tables may be selected at library initialization time.
  • Some of the globally visible functions and macros have been renamed or moved into the MEDDLY namespace to avoid conflicts.
  • Several example applications run faster now. This resolves the known issue under version 0.6.233.

New in Version 0.6.233 (released 05 Jul 2011)

Changes to the simple interface

  • The compute manager class has been removed; all its functionality has been moved to the MEDDLY namespace. For example, the old code segment 
    compute_manager* CM = getComputeManager();
CM->apply(compute_manager::UNION, x, y, z);

    can be replaced by

    apply(UNION, x, y, z);
  • The types of the operation codes (e.g., UNION) have changed. Most applications should not be affected by this; however, the change is visible to the simple interface.
  • A call to MEDDLY::cleanup() will automatically destroy any remaining domains, forests, or other objects created by MEDDLY. (This known issue listed under version 0.5 seems to be resolved.)
  • A few operation names have changed: old MIN is now MINIMUM and old MAX is now MAXIMUM.

Changes to the expert interface

  • Operation codes are now classes instead of an enumerated type. Each operation knows its own name and how to build an operation for specified forests (more on that, below).
  • The old operation and op_info classes have been merged together into a new operation class. Each instance of operation is tied to specific forests.
  • There are operation subclasses for unary, binary, and numerical operations. A numerical operation is tied to specific forest edges.
  • Numerical operations have moved to the expert interface, and are accessed as follows. Old code: 
    // preprocessing
compute_manager* CM = getComputeManager();
// ...
// critical
CM->vectorMatrixMultiply(y, y_ind, x, x_ind, A);

    New code:

    // preprocessing
numerical_operation* VM = VECT_MATR_MULT->buildOperation(y_ind, A, x_ind);
// ...
// critical
VM->compute(y, x);
  • Users may define their own operations in user space, and initialize them with the same mechanism as the built-in operations. To do this:
    1. Derive a class from op_initializer and implement the required virtual functions.
    2. Insert your initializer into the instance of settings used to initialize the library. If you want to initialize the builtin operations, you should use something like 
      MEDDLY::settings s;
s.operationBuilder = new my_initializer(s.operationBuilder);
MEDDLY::initialize(s);
    3. Your initializer’s initChain method will be called during the call to MEDDLY::initialize(s);
    4. Your initializer’s cleanupChain method will be called during the call to MEDDLY::cleanup();

Known Issues

  • The current compute table is not as fast as the old one for some operations.

New in Version 0.5.186 (released 16 Jun 2011)

New Features

  • Variables in domains are represented by instances of class variable, instead of integers. The same variable may appear in more than one domain.

  • Domain levels are always in the order: topmost, …, 2, 1, 0 where level 0 is for terminal nodes. As such, level mapping is no longer necessary.

  • For convenience, there is a new function 
    MEDDLY::createDomainBottomUp(...)

    which combines domain creation and variable initialization.

  • There are new functions to destroy objects, 
    MEDDLY::destroyDomain(...)
MEDDLY::destroyForest(...)

    and these must be used instead of delete.

Deprecated Functions

Now deprecated Equivalent replacement
domain::getTopVariable() domain::getNumVariables()
domain::getVariableAbove(v) v+1
domain::getVariableBelow(v) v-1
expert_domain::getVariableHeight(v) v
expert_domain::getVariableWithHeight(h) h

Known Issues

  • Calling MEDDLY::cleanup() can sometimes cause a segmentation fault. Destroying all domains before calling cleanup() seems to fix this.

New in Version 0.4.174 (released 13 Jun 2011)

  • Functions and classes are now contained in a MEDDLY namespace.

  • Top-level functions named MEDDLY_function have been renamed as function. For example, MEDDLY_createDomain() can now be called as MEDDLY::createDomain(), or as createDomain() inside a using namespace MEDDLY block.

  • There is a single, centralized error class. All methods that previously returned error now return void, and any errors are passed back to the user using throw. For example, the old code fragment 
    domain::error e = dom->createVariablesBottomUp(vars, N);
if (e != domain::SUCCESS) {
  fprintf(stderr, "Error: %s\n", domain::getErrorCodeName(e));
  exit(1);
}

    now becomes

    try {
  dom->createVariablesBottomUp(vars, N);
}
catch (MEDDLY::error e) {
  fprintf(stderr, "Error: %s\n", e.getName());
  exit(1);
}
  • The library must be initialized before use. (Most operations will fail and throw an appropriate error, otherwise.) This can be done via 
    MEDDLY::initialize();

    which uses default settings. To use different settings:

    MEDDLY::settings s;
// change members of s here;
// the constructor will fill everything with default values so
// it is only necessary to specify the non-default values.
MEDDLY::initialize(s);

  • compute_manager::setHashTablePolicy() has been removed, as this functionality is now provided using the appropriate settings during library initialization.

  • Library memory may be released using 
    MEDDLY::cleanup();

    Most operations will fail and throw an appropriate error after cleanup() is called. If desired, the library may be initialized again.

New in Version 0.3.165 (released 08 Jun 2011)

  • Added row-wise and column-wise iterators for Matrix Diagrams.

  • Iterators can now return the terminal value of the corresponding minterm.

  • Added (basic) vector matrix multiplication operations.

  • Improved batch addition of minterms based on Radix Sort (speed).
  • Added mechanism for building temporary nodes.

  • Added another option for batch addition of minterms based on temporary nodes.

  • Added reverse reachability (all states that can reach a given set of states using a given next-state function).

  • Added the traditional reachability algorithm and a saturation-based algorithm for reverse reachability.

  • Added test directory and files for make check.
  • Reorganization of source files.

Version 0.2.101 (released 11 Jun 2010)

  • First tarball release
  • CTL model checking functionality is complete (some advanced features are still in development)