On Fri, Jul 22, 2022 at 12:10 PM Richard Sandiford via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > 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?
OK. > 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<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 > -- > 2.25.1 >
