Binary Decision Diagram (BDD) library for JavaScript and TypeScript

binary-decision-diagram is a JavaScript and TypeScript library to create, minimize and optimize binary decision diagrams (BDDs). Build a reduced ordered binary decision diagram (ROBDD) or multi-terminal BDD (MTBDD) from a truth table, find a good variable ordering, serialize it to a tiny string and resolve values with it in the browser or in Node.js.

Table of contents

• What is a binary decision diagram?
• Features
• Installation
• Quick start
• API
• Use cases
• Further reading

What is a binary decision diagram?

A binary decision diagram (BDD) is a data structure that represents boolean functions in a compact way. It is a directed acyclic graph where every internal node tests one boolean variable and every leaf holds a result value. By merging identical subgraphs and removing redundant tests (the reduction and elimination rules), a decision tree with 2^n leaves often shrinks to a few nodes. This is called a reduced ordered binary decision diagram (ROBDD).

The size of a BDD depends heavily on the variable ordering, the order in which the boolean functions are tested. Finding a good ordering is the main way to make a BDD small, and this library ships a fast deterministic optimizer for it.

This library builds multi-terminal BDDs: the leaves can hold any number, not only true and false. That makes it a good fit to compile large truth tables or decision tables into small, fast lookup structures.

Features

• Create a BDD from a truth table (Map<string, number>)
• Minimize it with the reduction and elimination rules (ROBDD)
• Multi-terminal leaves: map every input combination to a number, not only to a boolean
• Deterministic variable ordering optimization, with proven optimal results for small tables
• Optimize for the expected runtime cost of the boolean functions, not only for the node count
• Don't-care values to remove rows that can never occur
• Pack a BDD into a typed array, ship it as a short base64 string and resolve it without parsing, ideal for small client-side bundles
• Written in TypeScript, ships ESM and CommonJS builds with type definitions

Installation

npm install binary-decision-diagram --save

Quick start

import {
    createBddFromTruthTable,
    bddToPackedBdd,
    packedBddToBase64String,
    packedBddFromBase64String,
    resolveWithPackedBdd,
    type ResolverFunctions
} from 'binary-decision-diagram';

// every key is one combination of the boolean functions, the value is the result
const truthTable = new Map<string, number>();
truthTable.set('00', 1);
truthTable.set('01', 3);
truthTable.set('10', 2);
truthTable.set('11', 1);

const bdd = createBddFromTruthTable(truthTable);
bdd.minimize();

// one boolean function per character of the truth table keys
const resolvers: ResolverFunctions<{ a: boolean; b: boolean }> = {
    0: (input) => input.a,
    1: (input) => input.b
};
bdd.resolve(resolvers, { a: true, b: false }); // 2

// store the BDD as a small string and resolve it without creating the nodes again
const packedBddString = packedBddToBase64String(bddToPackedBdd(bdd));
const packedBdd = packedBddFromBase64String(packedBddString);
resolveWithPackedBdd(packedBdd, resolvers, { a: true, b: false }); // 2

API

createBddFromTruthTable()

Creates a BDD from a truth table. The Truth-Table is a Map<string, number> where the string is a truth-set like 1101 and the number is the value.

const truthTable = new Map();
truthTable.set('00', 1);
truthTable.set('01', 3);
truthTable.set('10', 2);
truthTable.set('11', 1);

const bdd = createBddFromTruthTable(
    truthTable
);

minimize()

Reduces the nodes of a BDD by applying the reduction- and elimination rules.

bdd.minimize(
    false // if true, logs stuff (optional)
);

countNodes()

Returns the amount of nodes of the BDD.

bdd.countNodes(); // returns a number

removeIrrelevantLeafNodes()

Removes all irrelevant leaf-nodes with the given value.

// this will remove all leaf-nodes with the value of 5
bdd.removeIrrelevantLeafNodes(5);

resolve()

Resolves a state by calling the boolean functions through the nodes.

The resolve-functions is an object with the truth-table-value as key and a boolean function as value.

const resolvers: ResolverFunctions = {
    1: (i) => true,
    2: (i) => true,
    3: (i) => false
};

const bddValue = bdd.resolve(
    resolvers, 
    i // input that is passed to the resolvers
); // returns a value from the truth table

Packed BDD (for production)

The recommended way to ship an optimized BDD to production is the packed base64 string.

bddToPackedBdd() stores the whole BDD in a single typed array (Uint8Array, Uint16Array or Uint32Array, the narrowest that fits). Each non-leaf node takes three entries [level, ref0, ref1], so a BDD with less than ~250 nodes only needs 3 bytes per node. resolveWithPackedBdd() walks directly over that array: no JavaScript objects have to be created on startup and resolving is fast. packedBddToBase64String() turns the typed array into a short base64 string that you can put into your source code. It only contains ASCII characters, so it never has to be escaped by bundlers or minifiers. The leaf values must be non-negative integers.

1. At build time, create the BDD, pack it and write the string into a source file:

import * as fs from 'fs';
import { bddToPackedBdd, packedBddToBase64String } from 'binary-decision-diagram';

const packedBddString = packedBddToBase64String(bddToPackedBdd(bdd));
fs.writeFileSync(
    'src/bdd.generated.ts',
    `export const PACKED_BDD_STRING = '${packedBddString}';\n`
);

2. At runtime, decode the string once with packedBddFromBase64String() and resolve with resolveWithPackedBdd(). Decoding uses the native Uint8Array.fromBase64() (or atob() where it does not exist yet) and takes a few microseconds. Do it lazily so it only runs when the BDD is used the first time:

import {
    packedBddFromBase64String,
    resolveWithPackedBdd,
    PackedBdd,
    ResolverFunctions
} from 'binary-decision-diagram';
import { PACKED_BDD_STRING } from './bdd.generated';

let packedBdd: PackedBdd | undefined;
export function resolveInput(resolvers: ResolverFunctions, input: any): number {
    if (!packedBdd) {
        packedBdd = packedBddFromBase64String(PACKED_BDD_STRING);
    }
    return resolveWithPackedBdd(packedBdd, resolvers, input);
}

Migrating from version 3: the minimal string and the SimpleBdd were removed. Replace bddToMinimalString() with packedBddToBase64String(bddToPackedBdd(bdd)), minimalStringToSimpleBdd() with packedBddFromBase64String(), resolveWithSimpleBdd() with resolveWithPackedBdd() and bdd.toSimpleBdd() with bddToPackedBdd(bdd). An old minimal string cannot be read anymore, create the BDD again (for example with createBddWithOrdering()) and pack it.

optimizeOrdering()

Deterministically finds a variable ordering (the order in which the boolean functions are tested) that gives a small BDD and returns the minimized BDD for it. Unlike optimizeBruteForce() it does not shuffle randomly: the same truth table always gives the same result, it needs seconds instead of hours, and for small enough tables it proves that no better ordering exists. How it works is described in docs/variable-ordering.md.

The truth table must contain all 2^n rows (n = length of the keys, at most 30). Fill the rows that can never occur with a don't-care value first. Time and memory grow with 2^n: tables with 17 or 18 boolean functions take a few seconds (up to about 10 seconds with functionCosts), 21 functions take about half a minute and 0.5 GB. The computation runs synchronously and blocks the event loop while it runs.

const dontCareValue = 42; // value of the rows that can never occur at runtime
const truthTable: TruthTable = new Map();
truthTable.set('00000', 1);
// ... the known rows
fillTruthTable(truthTable, 5, dontCareValue);

const result = await optimizeOrdering({
    truthTable,
    // (optional) the don't-care rows are resolved like removeIrrelevantLeafNodes() does it:
    // a branch that only leads to don't-care rows is replaced by its sibling
    dontCareValue,
    // (optional) orderings to start from, for example the result of a previous run
    initialOrderings: [[3, 0, 1, 2, 4]],
    // (optional) 'auto' (default) runs the exact search when there are at most 20 boolean functions
    // and the BDD found by the local search has at most 5000 nodes, true always runs it, false never
    exact: 'auto',
    // (optional) called whenever a better ordering was found
    onImprovement: ({ nodeCount, phase }) => console.log(phase + ': ' + nodeCount + ' nodes')
});

result.bdd;        // the minimized BDD, ready for bddToPackedBdd()
result.ordering;   // ordering[level] = index of the boolean function tested on that level
result.nodeCount;  // result.bdd.countNodes()
result.optimal;    // true when it is proven that no ordering gives fewer nodes for result.truthTable
result.truthTable; // the truth table with the don't-care rows resolved, same keys as the input, in row order

With don't-care rows, optimal refers to the way the don't-care rows were resolved in result.truthTable. Which values the don't-care rows get is decided by a heuristic, so another ordering can occasionally reach a smaller BDD by resolving them differently. For the same reason, rebuild the BDD from result.truthTable, not from the input table: createBddWithOrdering(result.truthTable, result.ordering).

When the boolean functions have different runtime costs, pass them and the optimizer minimizes the expected cost of one resolve() call (the costs of the functions that are actually called on the way from the root to the leaf, averaged over the rows) instead of the amount of nodes. Expensive functions then end up on the levels where they are needed least often.

const result = await optimizeOrdering({
    truthTable,
    dontCareValue,
    // cost of calling each boolean function, one entry per character of the truth table keys
    functionCosts: [1, 1, 50, 1, 20],
    // (optional) how often a row occurs at runtime, default: every row that is not a don't-care row equally often
    rowWeight: (key, value) => key.startsWith('1') ? 10 : 1
});

result.expectedCost; // expected cost of one resolve() call
result.optimal;      // true when it is proven that no ordering has a lower expected cost for result.truthTable

Among orderings with the same expected cost, fewer nodes are preferred, but this tie-break is not part of the proof.

Coming from optimizeBruteForce(): instead of afterBddCreation: bdd => bdd.removeIrrelevantLeafNodes(x), pass dontCareValue: x. The optimizer can only make use of the don't-care rows when it knows about them.

Use findOrdering() with the same options when you only need the ordering and not the BDD, and createBddWithOrdering(truthTable, ordering, dontCareValue) to build the minimized BDD for a known ordering without going through the full decision tree.

optimizeBruteForce()

Optimizes the sorting of the boolean functions by shuffling randomly. Prefer optimizeOrdering(), which is deterministic and much faster. Returns a promise with the best found BDD.

const optimizedResult = await optimizeBruteForce({
    truthTable,
    iterations: 10000,
    // hook that runs whenever a bdd is created (optional)
    afterBddCreation: (bdd: RootNode) => {
        bdd.removeIrrelevantLeafNodes(dontCareValue);
    },
    // hook that is triggered whenever a better bdd was found (optional)
    onBetterBdd: (res: OptimisationResult) => {
        const packedBddString = packedBddToBase64String(bddToPackedBdd(res.bdd));
        console.log('new string: ' + packedBddString);
    },
    // (optional) start with this BDD to optimize. If not set, will create an own one.
    initialBdd: myBdd
});

Use cases

• Compiling decision tables: turn a large truth table of business rules or query conditions into a small BDD that needs only a few boolean checks per lookup.
• Small client-side bundles: precompute and optimize the BDD at build time, ship it as a packed base64 string and resolve it with resolveWithPackedBdd().
• Event reduction in databases: event-reduce uses this library to decide how a query result changes on a write event, which powers the realtime queries of the RxDB JavaScript Database.

Further reading

• How the variable ordering optimizer works
• Introduction on BDDs
• Presentation on BDDs
• Implementation of ROBDD
• Binary decision diagram on Wikipedia