Fri, 24 Aug 2018 00:40:12 -0700 (PDT)

Related articles |
---|

From: | woong.jun@gmail.com |

Newsgroups: | comp.compilers |

Date: | Fri, 24 Aug 2018 00:40:12 -0700 (PDT) |

Organization: | Compilers Central |

References: | 18-08-001 18-08-003 |

Keywords: | optimize, analysis, books |

In-Reply-To: | 18-08-003 |

David Lovemore wrote:

*> On Thursday, August 16, 2018 at 1:41:12 PM UTC+1, woon...@gmail.com wrote:*

*> > The official errata for the book, Advanced Compiler Design and Implementation*

*> > by Steven Muchnik added, among other fixes, this line to the Tarjan's algorithm*

*> > to find maximal strongly connected components (SCCs) from a directed graph.*

*> >*

*> > All_SCC U= {{Stack[1]}}*

*> >*

*> > where I replaced with brackets an arrow to mean retrival of an element from a*

*> > sequence named Stack. ...*

*>*

*>*

*> I don't have the book, so I can't see implementation of*

*> Strong_Components.*

Strong_Components implements an algorithm essentially same to what

Tarjan's original paper specifies.

Strong_Components looks like this:

x is a parameter to denote a flowgraph node

LowLink(x) = Dfn(x) = NextDfn += 1

push x to Stack

for each y from x's successors do

if Dfn(y) = 0 then

Strong_Components(y)

LowLink(x) = min(LowLink(x), LowLink(y))

elif Dfn(y) < Dfn(x) and y is on Stack then

LowLink(x) = min(LowLink(x), Dfn(y))

fi

od

if LowLink(x) = Dfn(x) then // x is root of SCC

SCC is an empty set

while Stack is not empty do

z = top from Stack without popping

if Dfn(z) < Dfn(x) then

add set SCC to another set All_SCC

return

fi

pop from Stack

add z to SCC

od

add set SCC to set All_SCC

fi

*> But I believe the description of the algorithm on*

*> wikipedia is correct. I suggest comparing with that.*

*>*

*> https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm*

Thanks for the reference. I compared and found no differences.

If the line in question had come from the text instead of the errata,

I would not have posted this question. I still wonder why the author

decided to add the line that looks unnecessary.

Thanks.

--

Woong Jun (woong.jun at gmail.com)

http://code.woong.org

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.