Path: csiph.com!xmission!news.snarked.org!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: woong.jun@gmail.com
Newsgroups: comp.compilers
Subject: An added line to Tarjan's SCC algorithm in Muchnik's Advanced Compiler Design
Date: Wed, 15 Aug 2018 20:48:12 -0700 (PDT)
Organization: Compilers Central
Lines: 28
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <18-08-001@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="99951"; mail-complaints-to="abuse@iecc.com"
Keywords: books, question
Posted-Date: 16 Aug 2018 08:41:09 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:2105

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.

The full context (p.195) reads as

    ... some declarations and init code omitted...
    for each x from node sets do
        if Dfn(x) = 0 then
            Strong_Components(x,Succ)
        fi
    od
    All_SCC U= {{Stack[1]}}

The original paper has no such line and I failed to figure out when it is
necessary.

It seems to imply the stack has one node that should be added to the set of
SCCs, but AFAIK the stack should be empty when returning an initial call to
Strong_Components() above. What am I missing here, or is this another added bug
as ones for Tarjan's dominator algorithm?

Thanks in advance.