A library to create, minimize and optimize binary decision diagrams in JavaScript.
A binary decision diagram is a data structure that represents a set of boolean function in an efficient way. To learn more about it, follow these links:
npm install binary-decision-diagram --saveCreates 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.add('00', 1);
truthTable.add('01', 3);
truthTable.add('10', 2);
truthTable.add('11', 1);
const bdd = createBddFromTruthTable(
truthTable
);Reduces the nodes of a BDD by applying the reduction- and elimination rules.
bdd.minimize(
false // if true, logs stuff (optional)
);Returns the amount of nodes of the BDD.
bdd.countNodes(); // returns a numberRemoves all irrelevant leaf-nodes with the given value.
// this will remove all leaf-nodes with the value of 5
bdd.removeIrrelevantLeafNodes(5);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 tableReturns a string-representation of the BDD which can be used in the client side to have a small javascript-bundle. BDDs can be very big so an effective storage format was needed.
const minimalString = bddToMinimalString(bdd)Parses the minimal string into an SimpleBdd. The SimpleBdd very small and only can resolve stuff.
const simpleBdd = minimalStringToSimpleBdd(str);Resolves a value with the SimpleBdd and the ResolverFunctions.
resolveWithSimpleBdd(
simpleBdd,
resolvers,
key
);Optimizes the sorting of the boolean functions to get an optimal BDD. 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(unknownValueActionId);
},
// hook that is triggered whenever a better bdd was found (optional)
onBetterBdd: (res: OptimisationResult) => {
const bddMinimalString = bddToMinimalString(res.bdd);
console.log('new string: ' + bddMinimalString);
console.log('value mapping:');
console.dir(res.mapping);
},
// (optional) start with this BDD to optimize. If not set, will create an own one.
initialBdd: myBdd
});