# Binary decision diagrams (BDD) syntax error

I am new here (and to Mathematica) and would like to rebuild a simple binary decision diagram that I found here https://en.wikipedia.org/wiki/Binary_decision_diagram

A code has been provided as part of an answer to a related question (Binary decision diagrams (BDD)), but it seems to generate a syntax error when running it in Mathematica. Please see the code and error message below. Could anyone tell me what I have to do to fix it? Apologies in case this is a very simple question...

bf = BooleanConvert @ BooleanFunction[12432, 4][a, b, c, d]

(a && b && ! c) || (! a && b && c && d) || (b && ! c && ! d)


We can convert this to if-and-constants form:

BooleanConvert[bf, "IF"]

If[a,
If[b, If[c, False, True], False],
If[b, If[c, If[d, True, False], If[d, False, True]], False]]


Here's a function that converts a boolean function to its if-and-constants form, and visualizes it as a graph:

ClearAll[bddGraph];
bddGraph[bf_] :=
With[{eq = Replace[BooleanConvert[bf, "IF"], If -> List, ∞, Heads -> True]},
Graph[
(Labeled[#, Extract[eq, # ~ Append ~ 1]] & /@ Position[eq, _List])
~ Join ~
(Labeled[#, #] & /@ {True, False}),
Flatten[
{Labeled[# \[DirectedEdge] # ~ Append ~ 2, True],
Labeled[# \[DirectedEdge] # ~ Append ~ 3, False]} & /@
Position[eq, _List], 2]
/.
a_ \[DirectedEdge] b_ :>
a \[DirectedEdge] Extract[eq, b] /; BooleanQ[Extract[eq, b]]]]


Now we can visualize the decision tree:

bddGraph[bf] However, instead of seeing the graph, I got the following error message:

Syntax::sntxf: "!(*StyleBox[\"\\"\\\\"\\"\", \"MT\"])!(*StyleBox[!(#), \"MT\"])!(*StyleBox[\"\\"\\\\" cannot be followed by \\\\"\\"\", \"MT\"])!(*StyleBox[!(((\[ DirectedEdge])) ((# ~ Append ~ 2))), \"MT\"])!(*StyleBox[\"\\"\\\\".\\"\", \"MT\"])!(*StyleBox[!(\"\"), \"MT\"])"

Syntax::tsntxi: "!(*StyleBox[\"\\"\\\\"\\"\", \"MT\"])!(*StyleBox[!(\[ DirectedEdge]), \"MT\"])!(*StyleBox[\"\\"\\\\" is incomplete; more input is needed.\\"\", \"MT\"])!(*StyleBox[!(\"\"), \"MT\"])"

Syntax::sntxi: Incomplete expression; more input is needed.

• Could you provide the input values you use? I ran the code you've provided with arguments in a format of : {{0, 0, 0, 1}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 1, 1, 1}} and it produced no error. Dec 3, 2015 at 11:48
• I believe there is an issue in the way your Mathematica IDE has interpreted the code you've copy/pasted. Could you please provide the version of Mathematica, I believe this could be useful. Dec 3, 2015 at 11:54
• Thanks for the quick help! I am using Mathematica 7.0 Dec 3, 2015 at 12:24
• And yes, the input values I wanted to use were the same as in your case! Dec 3, 2015 at 12:26
• bddGraph[BooleanConvert@BooleanFunction[12432, 4][a, b, c, d]] works perfectly on my system: V10.2 running on OS X 10.10.2. Dec 5, 2015 at 2:36

Running V10.3 on OS X 10.10.2, I can find nothing wrong with the OP code. I do not get the error messages he reports.

However, I found this an interesting problem and worked my own way of producing a binary decision diagram. I did it in my usual pedestrian way and produce code much more prolix than brilliantly concise but rather opaque code posted in the question. I present my work here because it provides a second, completely independent solution, and I believe it has some virtues, the principal one being that my code is much easier to understand.

### Example data

vars = {"a", "b", "c", "d"};
expr = BooleanConvert[BooleanFunction[12432, 4] @@ vars, "IF"];


Note that I am using strings to identify the nodes. The reason for this will become clear if you read my code. Whether this is a good hack or not is open to debate.

### Functions

There a fair number of them. This is a divide-and-conquer approach.

indexExpr indexes the node identifiers to make them (temporarily) unique. It also builds vMap, an association that contains rules of the form <vertex-name> -> <vertex-index>.

indexExpr[expr_If] :=
Module[{k = 0, indexed, vMap = Association[]},
indexed =
Activate[
Inactivate[expr, If] /.
s_String :> (ss = s <> ToString[++k]; AssociateTo[vMap, ss -> k]; ss)];
vMap = Join[vMap, Association[{True -> ++k, False -> ++k}]];
{indexed, vMap}]


Before the graph can be drawn, the indices post-fixed onto the vertex labels must be removed, which is deindexVars job.

deindexVars[Rule[k_, v_String]] := Rule[k, StringReplace[v, DigitCharacter .. -> ""]]
deindexVars[x_] := x


makeGraph makes a recursive traversal of the nested If-forms to produce the arguments wanted by Graph. The labels for the terminal True and False nodes are tacked on after the recursion completes.

makeGraph[expr_If] :=
Block[{indexedExpr, vMap, edges = {}, elbls = {}, vlbls = {}},
{indexedExpr, vMap} = indexExpr[expr];
helper[vMap, indexedExpr];
vlbls =
Join[
deindexVars /@ vlbls,
{vMap[True] -> Placed[True, Below], vMap[False] -> Placed[False, Below]}];
Graph[edges, EdgeLabels -> elbls, VertexLabels -> vlbls]]


This handles the case where both the then branch and the else branch of an If-form are terminal.

helper[vertexMap_, If[s_, lf : (True | False), rt : True | False]] :=
Module[{lfEdge, rtEdge},
{lfEdge, rtEdge} =
{DirectedEdge[vertexMap[s], vertexMap[lf]],
DirectedEdge[vertexMap[s], vertexMap[rt]]};
edgeHelper[lfEdge, rtEdge];
AppendTo[vlbls, vertexMap[s] -> s];]


This handles the case where the then branch of an If-form continues and the else branch is terminal.

helper[vertexMap_, If[s_, lf : If_, rt : True | False]] :=
Module[{lfEdge, rtEdge},
{lfEdge, rtEdge} =
{DirectedEdge[vertexMap[s], vertexMap[lf[]]],
DirectedEdge[vertexMap[s], vertexMap[rt]]};
edgeHelper[lfEdge, rtEdge];
AppendTo[vlbls, vertexMap[s] -> s];
helper[vertexMap, lf];]


This handles the case where the then branch of the an If-form is terminal and the else branch continues.

helper[vertexMap_, If[s_, lf : True | False, rt_If]] :=
Module[{lfEdge, rtEdge},
{lfEdge, rtEdge} =
{DirectedEdge[vertexMap[s], vertexMap[lf]],
DirectedEdge[vertexMap[s], vertexMap[rt[]]]};
edgeHelper[lfEdge, rtEdge];
AppendTo[vlbls, vertexMap[s] -> s];
helper[vertexMap, rt];]


This handles the case where both the then branch and the else branch of an If-form continues.

helper[vertexMap_, If[s_, lf_If, rt_If]] :=
Module[{lfEdge, rtEdge},
{lfEdge, rtEdge} =
{DirectedEdge[vertexMap[s], vertexMap[lf[]]],
DirectedEdge[vertexMap[s], vertexMap[rt[]]]};
edgeHelper[lfEdge, rtEdge];
AppendTo[vlbls, vertexMap[s] -> s];
helper[vertexMap, lf];
helper[vertexMap, rt];]


That takes care of the recursion. There is one more function that carries out a simple common task for the helper variants.

edgeHelper[lf_, rt_] :=
(edges = Join[edges, {lf, rt}];
elbls =
Join[
elbls,
{lf -> Style[True, Background -> White],
rt -> Style[False, Background -> White]}];)


### Example

makeGraph[expr] 