Re: alg for "compacting" series-parallel graphs (yacc->BNF)?

Vladimir Alexiev wrote:
>
> Does anyone know of an algorithm to find a "compact representation" of
> a series-parallel graph? Eg
>
> -- a -- b -- c -- should -- b --
> / \ become / \
> ----- a ------- c ----- -- a ----------- c --
>
> The set of all paths from source to target should remain the same,
> while the number of nodes should be minimized.


It seems to me that this is equivalent to the problem of minimizing the
size of an algebraic expression with addition and non-commutative
multiplication. (The associative and distributive laws hold.)


Given a series parallel graph, we can recursively convert it into such
an expression by the following rules: if it's just one edge, then it's
just a single variable; if it's parallel at the top level, then it's the
sum of the expressions obtained recursively from each of the parallel
parts; if it's series at the top level, then it's a product of the
expressions obtained from each of the serial parts. Of course
parentheses may be necessary to preserve the order of evaluation.


This process can also be done in reverse too: given an expression, we
can recursively construct a series parallel graph. I'll omit the
details.


In this correspondence between s.p.graphs and expressions, the sum of
the weights of all paths from source to sink in the series parallel
graph is equal to the (non-commmutative) polynomial defined by the
expression.


It seems to me that converting your graph to an expression, simplifying
the expression so that it contains as few arithmetic operations as we
can manage, and then reconverting to a graph, is a way to solve your
problem. (The number of occurrences of variables is always one more than
the number of arithmetic operations in the expression.)


Applying this to your example above gives ac+abc and a(1+b)c
respectively. Clearly ac+abc simplifies to a(1+b)c, and they both define
the same polynomial, ac+abc in fact.


Now as to how to simplify an algebraic expression, may I suggest that
the literature on algorithms for algebra systems may provide a rich
source of possibilities. Mathematica, Maple, Macsyma, etc. have to do
this sort of thing a lot, or so I suspect. Even if there's no effcient
way to completely minimize the number of operations, there may be some
very good methods that work well for relatively small examples, which
may be all you need. I'd love to know what you find out if you pursue
this line of inquiry.


Hope this helps.
Carl Sturtivant.
--

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