A

**decision diagram** is a

dag with

exactly one

source node (a node with no incoming

edges).

Every node except

sinks has a

variable attached, the

sinks have constants attached. Edges are usually marked with constants, too

A decision diagram

represents a

function f:

** D** - >

** M**,

**D**,

**M** sets ; the variables at the

inner nodes represent the variables of the function, the constants are

elements of

**M**.

A decision diagram is

evaluated in the following way:

- The evaluation is started at the source node.
- At every node in evaluation the value of the variable of the node is checked. Then the outgoing edge is choosen which has the value of the variable attached. The sink node of the edge becomes the new node in evaluation.
- This is repeated until a sink is reached.
- The value of the sink is returned.

In fact, there are more complicated versions, which have

intervals or even additional functions attached to the edges or evaluate all outgoing edges, returning a function/value for every edge and combine the results by a fixed function.

The most important type are

binary decision diagrams.

And

decison trees are also decision diagrams.