How to resolve the algorithm Kosaraju step by step in the J programming language

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm Kosaraju step by step in the J programming language

Table of Contents

Problem Statement

Kosaraju's algorithm (also known as the Kosaraju–Sharir algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju. The same algorithm was independently discovered by Micha Sharir and published by him in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.

For this task consider the directed graph with these connections: And report the kosaraju strongly connected component for each node.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Kosaraju step by step in the J programming language

Source code in the j programming language

kosaraju=: {{
  coerase([cocurrent)cocreate''
  visit=: {{
    if.y{unvisited do.
      unvisited=: 0 y} unvisited
      visit y{::out
      L=: y,L
    end.
  }}"0
  assign=: {{
    if._1=y{assigned do.
      assigned=: x y} assigned
      x&assign y{::in
    end.
  }}"0
  out=: y
  in=: <@I.|:y e.S:0~i.#y
  unvisited=: 1#~#y
  assigned=: _1#~#y
  L=: i.0
  visit"0 i.#y
  assign~L
  assigned
}}


   kosaraju 1;2;0;1 2 4;3 5;2 6;5;4 6 7
0 0 0 3 3 5 5 7


kosarajud=: {{
  coerase([cocurrent)cocreate''
  visit=: {{
    if.y{unvisited do.
      unvisited=: 0 y} unvisited
      visit y{::out
      L=: y,L
    end.
  }}"0
  assign=: {{
    if.-.y e.;assigned do.
      assigned=: (y,L:0~x{assigned) x} assigned
      x&assign y{::in
    end.
  }}"0
  out=: y
  in=: <@I.|:y e.S:0~i.#y
  unvisited=: 1#~#y
  assigned=: a:#~#y
  L=: i.0
  visit"0 i.#y
  assign~L
  assigned
}}

   kosarajud 1;2;0;1 2 4;3 5;2 6;5;4 6 7
┌─────┬┬┬───┬┬───┬┬─┐
│0 2 1│││3 4││5 6││7│
└─────┴┴┴───┴┴───┴┴─┘


   ((<@I.@e."1 0)i.@#) 0 0 0 3 3 5 5 7
┌─────┬┬┬───┬┬───┬┬─┐
│0 1 2│││3 4││5 6││7│
└─────┴┴┴───┴┴───┴┴─┘

You may also check:How to resolve the algorithm Reverse words in a string step by step in the Run BASIC programming language
You may also check:How to resolve the algorithm Jump anywhere step by step in the 6502 Assembly programming language
You may also check:How to resolve the algorithm Bitmap/Flood fill step by step in the Ruby programming language
You may also check:How to resolve the algorithm Leap year step by step in the Draco programming language
You may also check:How to resolve the algorithm Primality by trial division step by step in the FALSE programming language