diff mbox series

graphds: Fix description of SCC algorithm

Message ID mpty1wltq4u.fsf@arm.com
State New, archived
Headers
Series graphds: Fix description of SCC algorithm |

Commit Message

Li, Pan2 via Gcc-patches July 22, 2022, 10:09 a.m. UTC 
  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(-)

Comments

Li, Pan2 via Gcc-patches July 22, 2022, 10:49 a.m. UTC | #1 
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
>
diff mbox series

Patch

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