From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id E15733857C5D for ; Fri, 22 Jul 2022 10:09:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E15733857C5D Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 0F0181063 for ; Fri, 22 Jul 2022 03:09:56 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.37]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 292E53F766 for ; Fri, 22 Jul 2022 03:09:55 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH] graphds: Fix description of SCC algorithm Date: Fri, 22 Jul 2022 11:09:53 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Status: No, score=-53.7 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 22 Jul 2022 10:09:57 -0000 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). OK to install? Richard gcc/ * graphds.cc (graphds_scc): Fix algorithm attribution. --- 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 -- 2.25.1