Re: Boolean expressions represented as directed graph

Steve Jones wrote:
>
> A simple example:
>
> A -+-> B -> C -+-> J
> +-> X -> Y -+
>
> would equate to:
>
> J = A and ( ( B and C) or ( X and Y ) )
>




Steve,


It depends on what you want your output to look like. Assuming this
is for automated C-code generation, or something similar, then you can
traverse your graph and label the nodes with boolean expressions,
using something like a BDD (Boolean Decision Diagram) -- there are
lots of good packages like Buddy available for doing this.


Doing a depth-first search of predecessors (a DFS on the dual graph)
from the terminal (assignment) nodes, and propogating the expression
by forming the disjunct of the values at all incoming nodes, then
conjuncting with the current node's value, would yield a BDD at the
terminal node which you could expand by walking the BDD tree and
rewriting it with C-style selection operators (x ? y : z).


Keep in mind that not all graphs would generate the simple Boolean
expressions you might be expecting -- if there are loops or
overlapping paths, some of the terms generated would be redundant
unless minimization exists. You might want to check that there are no
loops in the graph first (with Tarjan's algorithm for finding strongly
connected components).


Consider the difficulty with this graph:


    +-- b <--
    v |
x --> a --+--> Y


with a loop through B around "a". The expression denoted by this is
simply "Y := a". To resolve loops you would likely need to find a
fixpoint of the loop, which requires checking equivalence of the
underlying expressions (simple using BDD's, very hard using strings!).




Also, if the semantics of this visual designer are such that the
labels on the graph can be arbitrary program code, you want to watch
out for side-effects. Applying short-circuit evaluation to children of
a graph node is not deterministic unless you create a well-defined
ordering of children. For example, what is the effect of code
generated by this?


a +-> (if *c++ != 0) --+-> J
    +-> (if *b++ != 0) --+


Hope this helps,


- Kenn

Return to the comp.compilers page.
Search the comp.compilers archives again.