A decision diagram
is a dag
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 represent
s a function
- > M
sets ; the variables at the inner node
s represent the variables of the function, the constants are element
s of M
A decision diagram is evaluate
d 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 interval
s 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 diagram
And decison tree
s are also decision diagrams.