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.