Welcome to EVMDD Library for Python (pyevmdd)’s documentation!¶
Introduction to EVMDDs¶
An Edgevalued Multivalued Decision Diagram (EVMDD) [CS02] is a data structure that can be used to represent an arithmetic function, comparable to how Binary Decision Diagrams (BDDs) are used to represent logic functions. EVMDDs differ from BDDs in two ways: first, the variables on which the represented functions depend can be multivalued instead of only binary, and second, the resulting function values are not read from the leaf node(s) of the diagram, but rather from the traversed edges.
EVMDDs can be used in automated planning to represent cost functions of actions with statedependent costs [GKM15]. This representation allows, among others, (i) an efficient compilation to actions with stateindependent costs, which are generally easier to handle algorithmically, and (ii) a faithful representation of action costs during the computation of goaldistance heuristics.
As an example, consider the diagram in the following figure, representing the function \(f(A,B,C) = AB^2 + C + 2\) for variables \(A\) and \(C\) that can take values \(0\) or \(1\) each, and variable \(B\) that can take the values \(0\), \(1\), or \(2\). The variable ordering is \(A, B, C\).
To see why this EVMDD represents the function \(f(A,B,C) = AB^2 + C + 2\), consider the valuation \(A = 1\), \(B = 2\), and \(C = 0\). We would then like to be able to read the function value \(f(1,2,0) = 6\) from the EVMDD. This is possible by traversing the path from top to bottom corresponding to the given valuation and summing up the encountered edge weights (given in rectangular boxes in the figure). For \(A = 1\), \(B = 2\), and \(C = 0\), and starting with the dangling incoming edge of the topmost node, we get the desired value \(2+0+4+0 = 6\).
As can be seen in the figure, EVMDDs help detecting and exploiting independencies in the represented arithmetic function. For example, the \(AB^2\) part and the \(C\) part of the example function are additively decomposable and hence independent. As a consequence, the EVMDD allows to first take care of the \(AB^2\) part completely before independently taking care of the \(C\) part. Alternatively, for variable ordering \(C, A, B\), the \(C\) part could have been handled completely before the \(AB^2\) part. Notice also that if \(A=0\), then the \(AB^2\) part has to be zero and there is no point in branching over \(B\) any more. Therefore, on this EVMDD path, \(B\) is skipped.
For arithmetic functions from a finite set of finitedomain variables with ranges \(0, ..., D_i1\) to the whole numbers, reduced ordered EVMDDs always exist and are unique. The canonicity requirements are similar to those for BDDs (isomorphism reduction, Shannon reduction), and additionally, for each node, the smallest weight of an outgoing edge must be zero.
Below, we will distinguish between fully reduced and quasireduced EVMDDs. We call an EVMDD fully reduced if it is Shannonreduced in the usual sense (there is no node in the diagram such that all outgoing edges carry the same weight and lead to the same successor node). In contrast, we call it quasireduced if it is isomorphism reduced, but no Shannon reductions are performed, i.e., on each path from top to bottom, each variable is branched over exactly once. This may include branchings at nodes contributing no additional information, such that all outgoing edges carry the same weight zero and lead to the same successor node. Quasireduction instead of full reduction can be necessary when EVMDDs are used to compute heuristics in AI planning [GKM15].
[CS02]  Gianfranco Ciardo and Radu Siminiceanu.
Using EdgeValued Decision Diagrams for Symbolic Generation of Shortest Paths.
In Proc. FMCAD 2002. (PDF)

[GKM15]  (1, 2) Florian Geißer, Thomas Keller, and Robert Mattmüller.
Delete Relaxations for Planning with StateDependent Action Costs.
In Proc. IJCAI 2015. (PDF)

Introduction to the pyevmdd Library¶
The purpose of the pyevmdd project is to provide a lightweight, pure Python EVMDD library. It is still in a very early stage of development. So far, the following features are supported (but unstable):
 Internal EVMDD representation.
 EVMDD output as a Graphviz file plus visualization.
 Function evaluation.
 Arithmetic operations \(+\) (addition), \(\) (subtraction, unary negation), and \(*\) (multiplication) on EVMDDs.
 Choice between fully reduced and quasireduced EVMDDs.
 Input of arithmetic functions in Python syntax.
If you are looking for an excellent, mature, efficient, and general EVMDD library that you can use in a serious application, we strongly recommend you to first consider using MEDDLY instead of pyevmdd. Compared to pyevmdd, MEDDLY has many advantages:
 Higher performance (C++ instead of Python, more optimization)
 Higher stability
 More supported operations
The pyevmdd library is explicitly not meant to compete with MEDDLY, but rather to serve as a playground for small experiments with extremely small EVMDDs. Compared to the EVMDDs MEDDLY has to handle in typical application scenarios, the EVMDDs that result from cost functions in AI planning are relatively small, which is why we developed this little EVMDD playground in the first place.
We only recommend using pyevmdd instead of MEDDLY if you agree with all of the following points:
 I do not care about performance.
 I do not care about maturity or stability.
 I do not care about few supported EVMDD operations (addition, subtraction and multiplication are enough for me).
 I am fine with a library that needs Python 3, likely because my client code is written in Python 3 as well.
 I want a simple highlevel Python interface to EVMDDs.
 I want to easily visualize my EVMDDs.
 I want to avoid the hassle of installing/using/interfacing to a C++ library.
Installing the pyevmdd Library¶
The sources can be cloned from the following git repository:
This library has the following requirements and dependencies:
It requires Python 3.
 For EVMDD visualization, it requires Graphviz
 Additionally, under Linux, it requires
xdot
to display EVMDDs.  Under Mac OS X, EVMDDs are displayed in the Safari browser after
dot
conversion to SVG.
 Additionally, under Linux, it requires
Several planned features (variable orderings, EVMDD based action compilation, evaluation of relaxed/abstract states), will probably make use of the NetworkX library.
Using the pyevmdd Library¶
Example Script¶
Let us step through a small script that makes use of the interesting pyevmdd features:
#!/usr/bin/env python3
# * coding: utf8 *
from evmdd import term_to_evmdd, evaluate, EvmddVisualizer
# EVMDD construction
function_term = 'A*B*B + C + 2'
var_names = ['A', 'B', 'C']
var_domains = {'A': 2, 'B': 3, 'C': 2}
evmdd, manager = term_to_evmdd(function_term, var_names=var_names,
var_domains=var_domains, fully_reduced=True)
# EVMDD evaluation
valuation = {'A': 1, 'B': 2, 'C': 0}
value = evaluate(evmdd, valuation, manager)
print(value)
# EVMDD visualization
visualizer = EvmddVisualizer(manager)
visualizer.visualize(evmdd)
EVMDD Construction¶
To construct an EVMDD, first, we give the function term to be represented as an EVMDD, for instance \(AB^2 + C + 2\). The term must be given in Python syntax using only variable names, constants, addition, subtraction, and multiplication. Hence, we have to write:
function_term = 'A*B*B + C + 2'
Although the variable names are clear from the given function term, the desired variable ordering is not. To enforce the ordering \(A, B, C\), we state:
var_names = ['A', 'B', 'C']
This information is still insufficient to construct an EVMDD, since the variable domain sizes that determine the branching width at variable test nodes still need to be given. Let us assume that variables \(A\) and \(C\) can take two values each (\(0\) and \(1\)), and that variable \(B\) can take three values (\(0\), \(1\), and \(2\)):
var_domains = {'A': 2, 'B': 3, 'C': 2}
Putting all this together, we can generate the desired EVMDD:
evmdd, manager = term_to_evmdd(function_term, var_names=var_names,
var_domains=var_domains, fully_reduced=True)
The function term is a required argument. The rest is optional. If no variable
ordering is given, the lexicographic ordering is used. If no domain sizes are
given, they are assumed to be \(2\) for all variables. Finally, if
fully_reduced
is not specified, it is true by default, i.e., EVMDDs will
be fully reduced as opposed to quasireduced. The function term_to_evmdd
returns the generated EVMDD together with the EvmddManager responsible for
managing its variables.
EVMDD Evaluation¶
To determine function values, we first need the variable assignment for which we want to evaluate our function. Let us assume we want to know the value of the function \(f(A,B,C) = AB^2 + C + 2\), under the valuation \(A = 1\), \(B = 2\), and \(C = 0\). We first define the valuation:
valuation = {'A': 1, 'B': 2, 'C': 0}
Afterwards, we can compute \(f(1,2,0)\):
value = evaluate(evmdd, valuation, manager)
print(value)
As expected, this prints the number \(6\).
EVMDD Visualization¶
Finally, especially for debugging and for didactic purposes, it is useful to
have easy access to visualizations of EVMDDs. We use EvmddVisualizers
for
that purpose:
visualizer = EvmddVisualizer(manager)
visualizer.visualize(evmdd)
Depending on OS details, this visualizes the EVMDD using Graphviz and either
xdot
display or conversion to SVG and web browser display. Figure
EVMDD Example above was produced this way.
Note
The temporary files needed for visualization are not deleted after
use. DOT and SVG files are stored in /tmp/evmddgvz<UUID>.dot
and
/tmp/evmddgvz<UUID>.dot.svg
, respectively. Optionally, a file prefix
can be given as a named argument file_prefix
to visualize
. The
default corresponds to visualize(evmdd,
file_prefix='/tmp/evmddgvz<UUID>')
.
Planned Features and Applications¶
Planned features and applications of this library include:
 Evaluation of relaxed/abstract states in AI planning.
 EVMDDbased action compilation and integration with FastDownward translator.
 Experiments with (static) variable orders.
Public API Reference¶
The public API is still unstable and likely subject to changes in the future. Currently, it consists of three modules:
 A core module (
evmdd.evmdd
) responsible for the internal representation of EVMDDs, arithmetic operations on them, and computation of function values.  An input module (
evmdd.parser
) responsible for translating arithmetic function terms specified in Python syntax to EVMDDs.  An output module (
evmdd.graphviz
) responsible for dumping EVMDDs in Graphviz format and displaying them.
In the following, we give the API documentation of the three modules.
EVMDD Core Module¶
This core module is responsible for the internal representation of EVMDDs via Nodes and Edges, for arithmetic operations on them, and for the computation of function values.
It supports quasireduced and fully reduced EVMDDs, but does not allow mixing
them. Many functions and methods have an optional boolean parameter
fully_reduced
or is_fully_reduced
that determines whether they are
supposed to deal with fully reduced (if true) or quasireduced (if false)
EVMDDs.

evmdd.evmdd.
Edge
(*args, **kwargs)¶ An edge in an EVMDD, specifying weight and successor node.
The weight of an edge e is the partial function value associated with the variablevalue pair corresponding to e (conditional on variablevalue pairs at higher levels).
The successor succ of e is the next node reached by e, either a test node for the next variable, or the sink node.
Additionally, each edge e has a flag is_fully_reduced that denotes whether the EVMDD represented by this edge is fully reduced or only quasireduced. By default, EVMDDs are fully reduced.
The “dangling incoming edge” from the literature is also represented by an object of this class that is required to have exactly one child node in the collection succ, i.e.,
len(succ) == 1
must hold for this edge. Since EVMDDs can be identified by their dangling incoming edge, we do not need a separate EVMDD class, but rather use Edges to represent EVMDDs.

evmdd.evmdd.
Node
(*args, **kwargs)¶ A node in an EVMDD specifying level and children.
The level of a node n specifies how far from the sink node n is located. Level 0 is reserved for the sink node, and levels increase bottomup. The level of the topmost branching is the number of variables in the EVMDD (assuming that the EVMDD is quasireduced).
The sink node is identified as the unique node without any outgoing edges.
Notice that only for a given variable ordering, levels will uniquely correspond to variable names. EVMDDs are constructed independently of a list of variable names, and variable names only come into play when an EVMDD is evaluated.
The list of children holds edges to lowerlevel nodes for all values of the variable tested at this node. The list has to be ordered, and the index in this ordering is the domain value. I.e., if the current node represents a test of variable \(v\), and \(v\) can take the three values \(0\), \(1\), and \(2\), then children contains three edges to the successor nodes for the cases \(v=0\), \(v=1\), and \(v=2\), respectively, in that order.
Like Edges, Nodes keep track of whether they belong to a fully reduced or a quasireduced EVMDD via the flag is_fully_reduced.

class
evmdd.evmdd.
EvmddManager
(var_names, var_domains, fully_reduced=True)¶ Manager for EVMDDs taking care of variable names and orderings, variable domain sizes, and construction of basic EVMDDs representing numeric constants and variables.
The variable names var_names are given in the desired variable order.
The domain sizes are given as a separate list var_domains in the same ordering as the variable names, i.e., the \(i\)th entry in var_domains specifies the domain size of the \(i\)th variable in var_names. Note that var_domains only holds the domain sizes, not the domains themselves. We assume throughout that all variables have domains from \(0\) to var_domains[i]  1.
The EVMDDs generated and managed by this manager can be either fully reduced or quasireduced. They will be fully reduced iff the flag fully_reduced is set to true (default).

make_const_evmdd
(number)¶ Construct an EVMDD representing a given constant number.
This is the EVMDD with a single edge immediately leading to the sink node, labeled with the given constant as its edge weight.
 Args:
 number (int): a constant arithmetic function.
 Returns:
 Edge: the EVMDD representing the given number.

make_var_evmdd_for_var
(var_name)¶ Construct an EVMDD representing a given variable.
 Args:
 var_name (string): a variable name.
 Returns:
 Edge: the EVMDD representing the given variable according to the variable order of this manager.
 Note:
 Fails if the given variable name is not known.

var_name_of
(node)¶ Determine the variable name associated with a given node.
 Args:
 node (Node): an EVMDD node.
 Returns:
 string: the name of the variable associated with the given node.


evmdd.evmdd.
evaluate
(evmdd, valuation, manager)¶ Evaluate an EVMDD evmdd for given valuation valuation and EvmddManager manager.
This function traverses the given EVMDD from top to bottom, following the unique path consistent with valuation. Along the way, it adds up the encountered edge weights. In order to match the variable names mentioned in valuation to levels in the EVMDD, this function needs to have access to the variable ordering provided by the manager. At each interior node n, the variable name v associated with n is looked up by the manager, and the value that v has is looked up in valuation. Then, the corresponding edge is traversed.
 Args:
evmdd (Edge): an EVMDD.
valuation (dict[string>int]): a variablevalue mapping to be evaluated.
manager (EvmddManager): an EvmddManager that knows variable names and orderings.
 Returns:
 int: the value the function represented by evmdd has under valuation.
 Examples:
>>> var_names = ['A', 'B'] >>> var_domains = [2, 2] >>> manager = EvmddManager(var_names, var_domains) >>> >>> N00 = _make_sink_node() >>> N10 = Node(level=1, children=[Edge(weight=0, succ=N00), Edge(weight=1, succ=N00)]) >>> N11 = Node(level=1, children=[Edge(weight=0, succ=N00), Edge(weight=2, succ=N00)]) >>> N20 = Node(level=2, children=[Edge(weight=0, succ=N10), Edge(weight=1, succ=N11)]) >>> evmdd = Edge(weight=2, succ=N20) >>> >>> s = { 'A': 0, 'B': 0 } >>> evaluate(evmdd, s, manager) 2 >>> s = { 'A': 0, 'B': 1 } >>> evaluate(evmdd, s, manager) 3 >>> s = { 'A': 1, 'B': 0 } >>> evaluate(evmdd, s, manager) 3 >>> s = { 'A': 1, 'B': 1 } >>> evaluate(evmdd, s, manager) 5
Function Term Input Module¶
This input and parser module is responsible for translating arithmetic function terms specified in Python syntax to EVMDDs.

evmdd.parser.
term_to_evmdd
(function_term, **kwargs)¶ Translate a function term to the corresponding EVMDD.
The variable names in the desired variable ordering can be optionally specified. If no variable ordering is specified, the variable names are determined from the function term and ordered lexicographically.
Also, the user may optionally specify the domain sizes of the variables. If no domain sized are specified, they default to 2 for all variables.
 Args:
function_term (string): a function term in Python syntax using only constants, variables, addition, subtraction exponentiation to natural numbered powers, and multiplication.
**kwargs: optionally, the variable names in the desired ordering, var_names (list of strings), their domain sizes var_domains (dict from strings to ints), and a flag fully_reduced determining whether the EVMDD should be fully reduced or quasireduced.
 Returns:
 a tuple consisting of the corresponding EVMDD and its manager.
The following example code constructs the fully reduced EVMDD for the running example \(f(A,B,C) = AB^2 + C + 2\) for variable ordering \(A, B, C\) and evaluates it for the valuation \(A=1\), \(B=2\), and \(C=0\).
 Example:
>>> from .evmdd import evaluate >>> expr = 'A*B**2 + C + 2' >>> var_names = ['A', 'B', 'C'] >>> var_domains = {'A': 2, 'B': 3, 'C': 2} >>> evmdd, manager = term_to_evmdd( ... expr, var_names=var_names, ... var_domains=var_domains, fully_reduced=True) >>> valuation = {'A': 1, 'B': 2, 'C': 0} >>> evaluate(evmdd, valuation, manager) 6
The next example shows that this works across a range of function terms, variable orderings, valuations, and both for fully and quasireduced EVMDDs.
 Example:
>>> from itertools import permutations, product >>> from .evmdd import evaluate >>> >>> def collect_variables(function_term): ... variables = set() ... expression = ast.parse(function_term, mode='eval') ... for node in ast.walk(expression): ... if(type(node) == ast.Name): ... name = node.id ... variables.add(name) ... return variables ... >>> >>> exprs = [ ... '0', '1', ... 'A', 'B', '0*A', '2*A', '0*B', '2*B', ... 'A+B', 'B+A', '1A', '1B', ... 'A', 'AB', 'BA', '(A+B)', ... 'A*B + B', 'B + A*B', ... 'A*B*B + C + 2', 'A*B  17', ... 'A*B  A*B', 'AA', ... '1*(A+2)', 'A*(B+2)', 'A*(B+2)*(B+2) + C + 2', ... ] ... >>> domain_size = 4 >>> >>> all_results_as_expected = True >>> for expr in exprs: ... var_set = collect_variables(expr) ... var_domains = {var: domain_size for var in var_set} ... for fully_reduced in [True, False]: ... for var_names in permutations(var_set): ... for valuation in product(range(domain_size), repeat=len(var_set)): ... valuation = {var:val for var, val in zip(var_names,valuation)} ... evmdd, manager = term_to_evmdd(expr, ... var_names=var_names, var_domains=var_domains, ... fully_reduced=fully_reduced) ... actual = evaluate(evmdd, valuation, manager) ... expected = eval(expr, valuation) ... if actual != expected: ... all_results_as_expected = False ... >>> all_results_as_expected True
Visualization/Output Module¶
Graphviz output and display of EVMDDs.

class
evmdd.graphviz.
EvmddVisualizer
(manager)¶ Helper class that displays EVMDDs on the screen.

visualize
(evmdd, file_prefix=None)¶ Visualize a given EVMDD.
The given EVMDD is first exported in Graphviz/DOT syntax and written to a temporary DOT file. Then, depending on the OS, the DOT file is either displayed using xdot (under Linux), or converted to SVG using dot and subsequently openend in a Browser (Safari, under Mac OS X).
In both cases, we assume that Graphviz is installed.
Notice that generated DOT/SVG files are not deleted after visualization.
 Args:
evmdd (Edge): the EVMDD to be visualized.
file_prefix (string, optional): path and file name of dot file to write to (
/tmp/evmddgvzUUID
by default) Returns:
 None
 Side effect:
 visualization of the given EVMDD.

License¶
Copyright (C) 2016 Robert Mattmüller
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>