Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Reduced ordered decision diagrams: share identical rule branches

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A reduced ordered binary decision diagram represents a Boolean rule as a directed acyclic graph. Every internal node tests one variable, with low and high branches for false and true; both paths respect the same variable order. Two reduction rules shrink the graph: a node whose branches are equal is removed, and an identical (variable,low,high) triple reuses one existing node from a unique table. Terminal IDs zero and one mean false and true. This teaching constructor enumerates every assignment to a pure predicate before interning nodes. It supports evaluation and sharing, not a full symbolic apply package or variable reordering engine.

Operational case

A dispatch rule permits an override or the conjunction of paid and approved. The three-variable diagram contains three internal nodes in the chosen order. A paid and approved request passes without override; paid without approval fails; override alone passes. Supplying an incomplete flag map is rejected, rather than silently interpreting omitted fields as false. The unique-table key includes the variable and both children; using only the children would merge tests of different variables and change the function. Choosing a different variable order can change graph size even when the rule's truth table stays the same.

Working Python program

python
class DispatchRuleDiagram:
    def __init__(self, variable_order, predicate):
        self.variables = tuple(variable_order)
        if len(set(self.variables)) != len(self.variables):
            raise ValueError("variable names must be unique")
        self.nodes = {}
        self.unique = {}

        def build(level, assignment):
            if level == len(self.variables):
                return int(bool(predicate(assignment)))
            variable = self.variables[level]
            assignment[variable] = False
            low = build(level + 1, assignment)
            assignment[variable] = True
            high = build(level + 1, assignment)
            del assignment[variable]
            if low == high:
                return low
            identity = (variable, low, high)
            if identity not in self.unique:
                node_id = len(self.nodes) + 2
                self.unique[identity] = node_id
                self.nodes[node_id] = identity
            return self.unique[identity]

        self.root = build(0, {})

    def permits(self, flags):
        if set(flags) != set(self.variables):
            raise ValueError("assignment must name every variable once")
        node_id = self.root
        while node_id > 1:
            variable, low, high = self.nodes[node_id]
            node_id = high if flags[variable] else low
        return bool(node_id)


if __name__ == "__main__":
    rule = DispatchRuleDiagram(
        ["override", "paid", "approved"],
        lambda flags: flags["override"] or (flags["paid"] and flags["approved"]),
    )
    print(len(rule.nodes), rule.permits({"override": False, "paid": True, "approved": True}))
    print(rule.permits({"override": False, "paid": True, "approved": False}))
    print(rule.permits({"override": True, "paid": False, "approved": False}))

Output

Output
3 True
False
True

Time, space, and tradeoff

Enumerating all assignments costs O(2^V) predicate evaluations for V variables in this direct constructor, and the resulting graph can have exponentially many distinct nodes. Evaluation follows at most V tests and uses O(1) extra state. The unique table uses expected hash lookup and O(M) space for M retained internal nodes, plus recursion and a mutable assignment map while building. Equivalent rules can share a canonical graph only under the same variable order and reduction conventions. A plain if-statement is simpler for one small rule; this structure helps when many related Boolean functions reuse subgraphs or require equivalence checks.

Common Mistakes

  • Do not intern two nodes with different variable names as the same decision.
  • Do not omit the rule that discards equal low and high branches.
  • Do not treat missing input flags as false without an explicit policy.
  • Do not claim a small graph for every variable order and predicate.

Connected lessons

Compare its query and update boundary with Fibonacci heaps: cut on decrease and consolidate on removal, Tournament trees: merge sorted runs through one winner path, Priority search trees: report events in a three-sided region, then complete the structure audit and decision quiz.

Zero-suppressed diagrams: share sparse dispatch set families adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details