From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1130) id BE7323857C5D; Fri, 22 Jul 2022 14:06:09 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BE7323857C5D MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Sandiford To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-1799] graphds: Fix description of SCC algorithm X-Act-Checkin: gcc X-Git-Author: Richard Sandiford X-Git-Refname: refs/heads/trunk X-Git-Oldrev: 18ef76d3a1701c4dd7ab38ebda5c374b6bc13041 X-Git-Newrev: 41da4070a2acd9a9c1a24446d1a670bc70462886 Message-Id: <20220722140609.BE7323857C5D@sourceware.org> Date: Fri, 22 Jul 2022 14:06:09 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 22 Jul 2022 14:06:09 -0000 https://gcc.gnu.org/g:41da4070a2acd9a9c1a24446d1a670bc70462886 commit r13-1799-g41da4070a2acd9a9c1a24446d1a670bc70462886 Author: Richard Sandiford Date: Fri Jul 22 15:05:57 2022 +0100 graphds: Fix description of SCC algorithm graphds_scc says that it uses Tarjan's algorithm, but it looks like it uses Kosaraju's algorithm instead (dfs one way followed by dfs the other way). gcc/ * graphds.cc (graphds_scc): Fix algorithm attribution. Diff: --- gcc/graphds.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/gcc/graphds.cc b/gcc/graphds.cc index f4c83e81cf9..91a2ca5c225 100644 --- a/gcc/graphds.cc +++ b/gcc/graphds.cc @@ -276,7 +276,7 @@ graphds_dfs (struct graph *g, int *qs, int nq, vec *qt, } /* Determines the strongly connected components of G, using the algorithm of - Tarjan -- first determine the postorder dfs numbering in reversed graph, + Kosaraju -- first determine the postorder dfs numbering in reversed graph, then run the dfs on the original graph in the order given by decreasing numbers assigned by the previous pass. If SUBGRAPH is not NULL, it specifies the subgraph of G whose strongly connected components we want