Version History

Changes since last release

Nothing yet

New in Version 0.15.0 (2018 May 22)

Simple Interface

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

Expert Interface

Various improvements and extensions to Saturation implementation.

Implementation

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 (2017 July 05)

Simple interface

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

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

Node storage styles are now set up using an initializer_list.

New in Version 0.13.685 (2016 June 15)

Simple interface

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

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

Fixed several bugs with node reference counts.

New in Version 0.12.625 (2015 April 25)

Simple interface

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

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

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 (2014 February 04)

Simple interface

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

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

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

New in Version 0.10.456 (2013 July 30)

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 (2012 July 26)

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 (2012 June 18)

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 (2011 July 15)

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 (2011 July 05)

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 ne 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 (2011 June 16)

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 (2011 June 13)

CHANGES TO THE SIMPLE INTERFACE

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 (2011 June 08)

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.

0.2.101 (2010 June 11)

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