3
$\begingroup$

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]

bdd

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – e.doroskevic Dec 3 '15 at 11:48
  • $\begingroup$ 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. $\endgroup$ – e.doroskevic Dec 3 '15 at 11:54
  • $\begingroup$ Thanks for the quick help! I am using Mathematica 7.0 $\endgroup$ – matts4 Dec 3 '15 at 12:24
  • $\begingroup$ And yes, the input values I wanted to use were the same as in your case! $\endgroup$ – matts4 Dec 3 '15 at 12:26
  • $\begingroup$ bddGraph[BooleanConvert@BooleanFunction[12432, 4][a, b, c, d]] works perfectly on my system: V10.2 running on OS X 10.10.2. $\endgroup$ – m_goldberg Dec 5 '15 at 2:36
3
$\begingroup$

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[[1]]]], 
       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[[1]]]]};
    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[[1]]]], 
       DirectedEdge[vertexMap[s], vertexMap[rt[[1]]]]};
    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]

graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.