public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r13-1799] graphds: Fix description of SCC algorithm
@ 2022-07-22 14:06 Richard Sandiford
  0 siblings, 0 replies; only message in thread
From: Richard Sandiford @ 2022-07-22 14:06 UTC (permalink / raw)
  To: gcc-cvs

https://gcc.gnu.org/g:41da4070a2acd9a9c1a24446d1a670bc70462886

commit r13-1799-g41da4070a2acd9a9c1a24446d1a670bc70462886
Author: Richard Sandiford <richard.sandiford@arm.com>
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<int> *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


^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2022-07-22 14:06 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-22 14:06 [gcc r13-1799] graphds: Fix description of SCC algorithm Richard Sandiford

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).