Re: iterative data flow question



"Jeremy Wright" <Jeremy.Wright@xxxxxxxxxxxxxx> writes:

... I have yet to come up with an example
where a forward PO does not correspond to a reverse RPO (for graphs with
single entry and exit).

More generally, if PO() and RPO() return the set of all possible
[reverse] post orders of a graph, and rev() returns the graph with the
control flow edges reversed, is there a graph G such that

PO(G) != RPO(rev(G))


Consider a directed graph on four nodes A, B, C, and D, with A being
the entry and D being the exit, and with edges

A->B
B->C
B->D
C->B.

A diagram may make this clearer:

A -> B -> D.
^
|
V
C

Not only are the sets PO(G) and RPO(rev(G)) unequal, they are in fact
completely disjoint. Whether the graph is traversed forward or
reversed, C will be retreated out of before B is. Thus in any
postorder of either the graph or its reversal, C precedes B, whereas
in any reverse postoder of either the graph or its reversal, C follows
B.

-Max Hailperin
Professor of Computer Science
Gustavus Adolphus College
http://www.gustavus.edu/+max/
.



Relevant Pages

  • iterative data flow question
    ... control flow graph. ... order is RPO on the reverse CFG. ...
    (comp.compilers)
  • A determininistic four-coloring algorithm.
    ... can be used to reliably color the graph using four colors without ... Continue coloring any adjacent vertices using only these three ... If the edges are of set D, then identify a Kempe chain of colors D ... vertex, and reverse it. ...
    (sci.math)
  • Re: A determininistic four-coloring algorithm.
    ... Fully triangulate the graph by adding either edges or vertices (it ... Continue coloring any adjacent vertices using only these three ... If the edges are of set D, then identify a Kempe chain of colors D ... vertex, and reverse it. ...
    (sci.math)
  • Graph reverse order changes series order but not legend order
    ... If I change the order of a graph in the axis properties the order of ... Is there any way to reverse the order of the graph ... and keep the series order synchronized with the legend order besides ...
    (microsoft.public.excel.misc)
  • Re: TROUBLE with CUSTOM ANIMATIONS
    ... is whether you have used an exit animation that works on pieces of the graph ... as well as on the whole graph. ... > for my slide show. ...
    (microsoft.public.powerpoint)