Re: Boolean expressions represented as directed graph

"VBDis" <>
31 May 2002 23:07:19 -0400

          From comp.compilers

Related articles
Boolean expressions represented as directed graph (Steve Jones) (2002-05-27)
Re: Boolean expressions represented as directed graph (VBDis) (2002-05-31)
Re: Boolean expressions represented as directed graph (Kenn Heinrich) (2002-05-31)
| List of all articles for this month |

From: "VBDis" <>
Newsgroups: comp.compilers
Date: 31 May 2002 23:07:19 -0400
Organization: AOL Bertelsmann Online GmbH & Co. KG
References: 02-05-149
Keywords: design
Posted-Date: 31 May 2002 23:07:19 EDT

"Steve Jones" <> schreibt:

>A -+-> B -> C -+-> J
> +-> X -> Y -+

First I had some problems with the meaning of this text, without an fixed size
font ;-)

>I'm looking for some insight on the approach I might take in traversing the
>graph to convert it to the text form.

I'd use an array with the number of not yet seen in-edges for every node. Then
walk the tree and create AND expressions for all sequences, and OR expressions
from all forks. Walking stops on a follow node with yet unseen in-edges, backs
up to the last fork, and processes the next edge. Processing continues only
when all in-edges to the next node already have been seen. Parentheses should
be inserted around every OR subexpression, starting at a fork.

In your example first "A && ( B && C" is created. Then the follow node has
another yet unseen in-edge, which results in a backup to A. Then walking the
next branch results in " || X && Y", and continues with ")", since now all
in-edges of J have been seen, and with the final assignment. I'd remove the
assignment from the graph before, and replace it by an synthetic end node,
because it's a different (non boolean) operation.


Post a followup to this message

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