6 Mar 1998 16:54:56 -0500

Related articles |
---|

alg for "compacting" series-parallel graphs (yacc->BNF)? vladimir@cs.ualberta.ca (Vladimir Alexiev) (1998-03-03) |

Re: alg for "compacting" series-parallel graphs (yacc->BNF)? carl@bitstream.net (Carl Sturtivant) (1998-03-06) |

Re: alg for "compacting" series-parallel graphs (yacc->BNF)? joachim.durchholz@munich.netsurf.de (Joachim Durchholz) (1998-03-07) |

From: | Carl Sturtivant <carl@bitstream.net> |

Newsgroups: | comp.theory,sci.math,comp.compilers |

Date: | 6 Mar 1998 16:54:56 -0500 |

Organization: | Bitstream Underground |

Distribution: | inet |

References: | 98-03-015 |

Keywords: | theory |

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.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.